[Java][LeetCode][Blind75] 572. Subtree of Another Tree | Easy | Tree | Recursion

문제 / 예제 / 제한조건 :

node 에 subNode가 포함되어 있는지 판단하는 문제.

 

# 풀이

1. 두 노드가 null 인지 확인 -> True

2. 두 노드 중 한 노드만 null -> False

3. 두 노드의 값이 같으면 -> 같은 노드인지 확인 (isSameTree 문제해서 사용했던 함수를 사용하면 된다 - https://codingstorywithme.tistory.com/88)

4. 두 노드의 값이 다르면 -> 노드의 좌/우 로 이동해 같은 값을 찾아나가면 된다.

/**
 * 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) {
        return isSubtreeHelper(root, subRoot);
    }

    private boolean isSubtreeHelper(TreeNode node, TreeNode subNode) {
    	// 1. 두 노드가 null 인지 확인 -> True
        if(node == null && subNode == null) return true;
        
        // 2. 두 노드 중 한 노드만 null -> False
        if(node == null || subNode == null) return false;

		// 3. 두 노드의 값이 같으면 -> 같은 노드인지 확인
        if(node.val == subNode.val
                && isSameTree(node, subNode)) {
            return true;
        } 
        // 4. 두 노드의 값이 다르면 -> 노드의 좌/우 로 이동해 같은 값을 찾아나가면 된다.
        else {
            return isSubtreeHelper(node.left, subNode)
                    || isSubtreeHelper(node.right, subNode);
        }
    }
    
    private boolean isSameTree(TreeNode node, TreeNode subNode) {
        if(node == null && subNode == null) return true;
        if(node == null || subNode == null) return false;
        
        if(node.val == subNode.val) {
            return isSameTree(node.right, subNode.right) && isSameTree(node.left, subNode.left);
        } else {
            return false;
        }
    }
}

Time Complexity: O(m * n)
Space Complexity: O(max(m, n))
* m : 이진 트리의 노드 수, n : 서브트리의 노드 수

 

깔끔하게 끝!