[NeetCode-LeetCode] Subtree of Another Tree JAVA

반응형

728x90

[NeetCode-LeetCode] Subtree of Another Tree - Easy

---

접근

• 재귀

---

풀이

어떤 트리 내부에 동일한 서브트리가 존재하는지 검사하는 문제이다. 정확하게 주어진 서브트리와 일치해야 한다 즉 기존 트리 내부에 서브트리와 동일한 부분이 존재하지만 밑에 추가로 자식 노드가 존재하거나 하는 경우엔 동일한 서브트리라 볼 수 없다. 

출처: LeetCode

위와 같은 형태에 왼쪽 트리에 4, 1, 2라는 동일한 구조가 있는데 2 노드 밑에 0이라는 자식 노드가 있기 때문에 다른 서브트리라 판단하고 false가 된다. 

    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }

        if (checkSameTree(root, subRoot)) {
            return true;
        }

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

root가 존재하지 않으면 false를 반환하고 checkSameTree라는 체크 메서드를 통해 체크를 한다. 만약 현재 루트에서 동일서브트리 체크에 실패하면 각자 자식 노드에 대해 다시 재귀적으로 체크하게 된다. 

    public boolean checkSameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }

        if (root == null || subRoot == null) {
            return false;  
        }

        return root.val == subRoot.val && checkSameTree(root.left, subRoot.left) && checkSameTree(root.right, subRoot.right);
    }

기존 노드의 root와 서브트리의 root가 둘 다 null이라면 서브트리 체크가 성공했다는 것으로 true를 반환한다. 둘 중의 하나라도 null이 아니라면 서브트리가 동일하지 않은 것으로 false를 반환한다. 두 노드가 null이 아니라면 값이 동일한지와 양쪽 서브트리에 대해서도 재귀적으로 진행해 준다. 

---

전체 코드

/**
 * 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 isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null) {
            return false;
        }

        if (checkSameTree(root, subRoot)) {
            return true;
        }

        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean checkSameTree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }

        if (root == null || subRoot == null) {
            return false;  
        }

        return root.val == subRoot.val && checkSameTree(root.left, subRoot.left) && checkSameTree(root.right, subRoot.right);
    }
}