[Easy] LeetCode - no.100 Same Tree : Java

https://leetcode.com/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

2개의 이진 트리 p와 q가 주어졌을 때, 두 이진 트리가 서로 동일한지 판단할 것

 

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

 

 

 

 

풀이

참고

[자바] Leetcode 100 - Same Tree

    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 false;
        }

        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }

• 재귀 사용
• 기저 조건
  • 1) p와 q 모두 null일 경우 : 동시에 끝에 도달했다는 뜻이니 true 반환
  • 2) p와 q 둘 중 하나만 null일 경우 : 깊이가 서로 맞지 않는다는 뜻이니 false 반환
  • 3) p.val과 q.val이 다를 경우 : 같은 트리일 수 없으니 false 반환
• p.left와 q.left, p.right와 q.right를 비교하여 둘 다 같을 경우를 판단 (&& 사용)
• 시간복잡도 : O(N) (두 트리의 모든 노드를 한 번씩 방문해야 하기 때문)