[LeetCode] 572. Subtree of Another Tree - Java

https://leetcode.com/problems/subtree-of-another-tree/description/

Subtree of Another Tree - LeetCode

---

문제

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.

 

Example 1:

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

Example 2:

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

 

Constraints:

• The number of nodes in the root tree is in the range [1, 2000].
• The number of nodes in the subRoot tree is in the range [1, 1000].
• -104 <= root.val <= 104
• -104 <= subRoot.val <= 104

---

풀이

풀이 과정

두 개의 트리 root, subRoot가 주어질 때 subRoot가 root에 포함되는 트리인지 판단하는 문제이다.

root의 값과 subRoot의 값이 같다면 두 트리가 같은 트리인지 비교하여 같은 트리이면 subRoot는 root에 포함되는 트리가 되고, 값이 다르다면 root의 왼쪽 값과 오른쪽 값을 차례대로 비교하며 같은 과정을 반복하면 된다.

주어진 두 트리가 같은 트리인지 탐색하는 알고리즘은 LeetCode의 100. Same Tree 문제 풀이를 참고한다.

[LeetCode] 100. Same Tree - Java

public boolean isSameTree(TreeNode tree1, TreeNode tree2) {
    // 두 노드가 모두 null인 경우
    // 현재 값이 같고 다음 노드를 탐색할 필요가 없으므로 true를  return
    if(tree1 == null && tree2 == null) return true;

    // 둘 중 하나의 노드만 null인 경우
    // 현재 노드가 다르므로 false를 return
    if(tree1 == null || tree2 == null) return false;

    // 값이 같지 않은 경우 false
    if(tree1.val != tree2.val) return false;

    // 값이 같으면 왼쪽 노드와 오른쪽 노드를 비교
    return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
}

 

이제 두 트리의 값이 같은 경우를 먼저 판단해야하는데, 우선 주어진 두 트리중 하나가 null인 경우는 비교가 불가능 하므로 false를 return 한다.

// 두 트리 중 하나가 null인 경우 비교가 불가능하므로 false를 return
if(root == null || subRoot == null) return false;

 

만약 두 트리의 값이 같은 경우 같은 트리인지 판단하여 같은 트리라면 true를 return 한다.
여기서 주의해야 할 점은 같은 트리가 아니라고 해서 결과값으로 바로 false를 return해서는 안된다.
트리의 각 노드 값이 유니크하지 않으므로 다음과 같은 케이스가 생길 수 있다.

위와 같은 트리에서 root의 첫 번째 노드와 subRoot를 비교할 때 두 트리는 같은 트리가 아니지만 root의 왼쪽 노드와 subRoot를 비교할 때 두 트리는 같은 노드이기 때문에 값이 같으면서 같은 트리가 아닌 경우에도 모든 노드를 탐색하도록 탐색을 계속 해야한다.

// 두 트리의 값이 같은 경우
if(root.val == subRoot.val ){
    // 같은 트리인지 비교, 같은 트리면 true를 return
    if(isSameTree(root, subRoot)) return true;
}
// root의 왼쪽과 오른쪽 값을 subRoot와 비교
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);

---

최종 코드

/**
 * 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) {
        // 두 트리 중 하나가 null인 경우 비교가 불가능하므로 false를 return
        if(root == null || subRoot == null) return false;

        // 두 트리의 값이 같은 경우
        if(root.val == subRoot.val ){
            // 같은 트리인지 비교, 같은 트리면 true를 return
            if(isSameTree(root, subRoot)) return true;
        }
        // root의 왼쪽과 오른쪽 값을 subRoot와 비교
        return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    public boolean isSameTree(TreeNode tree1, TreeNode tree2) {
        // 두 노드가 모두 null인 경우
        // 현재 값이 같고 다음 노드를 탐색할 필요가 없으므로 true를  return
        if(tree1 == null && tree2 == null) return true;

        // 둘 중 하나의 노드만 null인 경우
        // 현재 노드가 다르므로 false를 return
        if(tree1 == null || tree2 == null) return false;

        // 값이 같지 않은 경우 false
        if(tree1.val != tree2.val) return false;

        // 값이 같으면 왼쪽 노드와 오른쪽 노드를 비교
        return isSameTree(tree1.left, tree2.left) && isSameTree(tree1.right, tree2.right);
    }
}

---