[NeetCode-LeetCode] Same Tree JAVA

반응형

728x90

[NeetCode-LeetCode] Same Tree - Easy 

---

접근

• 재귀

---

풀이

주어진 두 트리가 같은 지 검증하면 되는 문제이다. 트리의 값과 형태를 기준으로 검증하기 때문에 재귀를 통해 같은 레벨 같은 위치에 같은 값이 존재하는지만 확인하면 되는 문제로 간단한 문제이다.

    public boolean isSameTree(TreeNode p, TreeNode q) {
        return checkSameTree(p, q);
    }

    private boolean checkSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        
        if (p == null || q == null || p.val != q.val) {
            return false;
        }

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

코드는 간단하다. 재귀를 통해 트리의 바닥까지 이동한 뒤 바닥에서부터 검증을 수행하게 된다. 두 노드가 모두 null 인 경우 바닥에 도달했다고 생각하고 검증을 시작하게 된다. 만약 두 노드 중 하나가 null 이거나 두 노드의 값이 다르다면 동일한 트리가 아니기에 false를 반환하게 된다. and 연산으로 결과를 반환하기 때문에 모든 값이 동일하지 않다면 false가 반환된다. 

---

전체 코드

/**
 * 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) {
        return checkSameTree(p, q);
    }

    private boolean checkSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        
        if (p == null || q == null || p.val != q.val) {
            return false;
        }

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