[LeetCode] 18.Same Tree

leetcode.com/problems/same-tree/

Same Tree - LeetCode

 

1. Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

 

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

 

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

 

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

 

Constraints:

• The number of nodes in both trees is in the range [0, 100].
• -104 <= Node.val <= 104

 

2. Code

package leetCode;

import java.util.ArrayList;
import java.util.List;

import sun.net.www.content.text.plain;

public class SameTree {
	 /* Definition for a binary tree node.
	 * public class TreeNode {
	 *     int val;
	 *     TreeNode left;
	 *     TreeNode right;
	 *     TreeNode() {}
	 *     TreeNode(int val) { this.val = val; }
	 *     TreeNode(int val, TreeNode left, TreeNode right) {
	 *         this.val = val;
	 *         this.left = left;
	 *         this.right = right;
	 *     }
	 * }
	 */
	public static void main(String[] args) {
		TreeNode p = new TreeNode(2);
		TreeNode pl = new TreeNode(2);
		TreeNode pr = new TreeNode(4);
		p.left = pl;
		p.right = pr;
		
		TreeNode q = new TreeNode(2);
		TreeNode ql = new TreeNode(2);
		TreeNode qr = new TreeNode(4);
		q.left = ql;
		q.right = qr;
		
		isSameTree(p, q);
	}
	
    public static boolean isSameTree(TreeNode p, TreeNode q) {
    	if(p == null || q == null) {
    		return false;
    	}
    	//System.out.println(p.val + " " + p.left.val + " " + p.right.val);
        List<Integer> pList = new ArrayList<>();
        List<Integer> qList = new ArrayList<>();
        arrListTree(pList, p);
        arrListTree(qList, q);

    	return pList.toString().equals(qList.toString());
    }

   public static List<Integer> arrListTree(List<Integer> listTree, TreeNode t) {
	   listTree.add(t.val);
	   
	   if(t.left != null) {
    		arrListTree(listTree,t.left);
    	} else if(t.left == null && t.right != null) {
    		listTree.add(null);
    	}
	   
    	if(t.right != null) {	
    		arrListTree(listTree, t.right);
    	}

    	return listTree;
    } 
}

 

 

3. Report

재귀를 이용해서 두 트리를 arrayList에 순서대로 담은 후 두 arrayList를 비교했다

처음 실수는 p=[1,2] q=[1,null,2]일때도 값이 같다고 나와서 오류가 났는데

왼쪽노드는 null이고 오른쪽 값이 있을때 arrayList에 null을 추가해주는 코드를 작성해줘서 해결했다

트리랑 재귀를 처음 써봤는데 100% 나왔다 기분이좋다