leetcode 100 (Same Tree) - Java

문제

두 이진 트리가 주어지면 동일한지 여부를 확인하는 함수 작성
두 개의 이진 트리는 구조적으로 동일하고 노드의 값이 동일한 경우 동일한 것으로 간주된다.

이진 트리가 동일하면 true, 그렇지 않으면 false를 반환하는 문제이다.

예시1![]

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

예시2

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

예시3

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

제약 조건

두 트리의 노드 수는 범위 내에 있습니다.[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 {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
         
        if(p == null  && q == null) return true;
        if(p == null || q == null)  return false;
        
        if(p.val == q.val) {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
        else 
            return false;  
    }
}

• p와 q가 모두 null 이면 둘다 null이므로 true를 반환한다.

• p와 q 둘 중 하나가 null이면 항상 같지 않으므로 false를 반환한다.

• p와 q의 노드의 값이 동일하다면 재귀를 통해 왼쪽 노드와 오른쪽 노드가 모두 같은지 확인하고 같으면 true, 아니면 false가 반환된다.

1은 같으므로 왼쪽 노드 비교 -> isSameTree(p.left, q.left)
2는 같으므로 true, 1의 오른쪽 노드 비교 -> isSameTree(p.right, q.right);
3은 같으므로 true.

모든 노드가 동일하므로 ture 반환.