Leet code (Easy): 572. Subtree of Another Tree - Java

 

트리와 서브 트리가 주어지고, 서브 트리가 트리 내에 있는지 찾는 문제다.

트리 내부에 서브 트리와 일치하는 부분이 있어야 하는데 그 부분 밑에 딸린 자식이 없어야한다.

 

 

1) BFS 풀이

/**
 * 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) {
        // subRoot가 null 이면 무조건 성립
        if(root == null && subRoot == null || root != null && subRoot == null){
            return true;
        }

        // root가 null 인데 subRoot가 null이 아니면 무조건 성립 x
        if(root == null && subRoot != null) return false;

        // Queue에 null은 안담김
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);

        while(!q.isEmpty()){
            TreeNode now = q.poll();
            if(isSame(now, subRoot)) return true;
            if(now.left != null) q.offer(now.left);
            if(now.right != null) q.offer(now.right);
        }

        return false;
    }

    // 재귀로 subTree와 일치하는지 확인 (BFS,DFS 동일)
    private boolean isSame(TreeNode root, TreeNode subRoot){
        if(root == null && subRoot == null) return true;
        if(root == null && subRoot != null || root != null && subRoot == null) return false;
        
        if(root.val != subRoot.val) return false;

        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }
}

 

 

2) DFS  풀이

/**
 * 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) {

        // subRoot가 null 이면 무조건 성립
        if(root == null && subRoot == null || root != null && subRoot == null){
            return true;
        }
        
        if(root == null && subRoot != null) return false;
        
        if(isSame(root, subRoot)) return true;

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

    // 재귀로 subTree와 일치하는지 확인 (BFS,DFS 동일)
    private boolean isSame(TreeNode root, TreeNode subRoot){
        if(root == null && subRoot == null) return true;
        if(root == null && subRoot != null || root != null && subRoot == null) return false;
        
        if(root.val != subRoot.val) return false;

        return isSame(root.left, subRoot.left) && isSame(root.right, subRoot.right);
    }
}