[JAVA] 100. Same Tree

목차

문제

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

풀이

/**
 * 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;
 *     }
 * }
 */
class Solution {

    boolean answer = true;

    public boolean isSameTree(TreeNode p, TreeNode q) {
        /**
            아이디어
            1. 트리 전체 순회하면서 동일여부 판단
            2. 재귀, 스택 사용가능하나 재귀 사용
        */
        recCheckTree(p, q);
        return answer;
    }

    public void recCheckTree(TreeNode p, TreeNode q){
        if(p != null && q != null){
            //양쪽 노드나 null이 아닌경우 판단
            if(p.val != q.val){
                answer = false;
            }
            recCheckTree(p.left, q.left);
            recCheckTree(p.right, q.right);
        }else if (p == null && q == null){
            //양쪽 노드가 둘다 null로 가는 경우, 같으므로 따로 처리 안함
        }else{
            //양쪽 노드가 null 포함하여 다른 경우, 다르다고 판단
            answer = false;
        }
    }
}