[LeetCode 해석 및 풀이] 572. Subtree of Another Tree (다른 트리의 서브트리)

LeetCode 문제 해석 및 풀이 방법

 

문제 572. Subtree of Another Tree (다른 트리의 서브트리)

바로가기

 

문제 설명

영문

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.

 

한글

두 개의 이진 트리의 뿌리 root와 subRoot가 주어질 때, root의 서브트리에 subRoot와 똑같은 구조와 값이 있다면 True를, 아니면 False를 반환하십시오.

 

이진 트리의 서브트리 tree는 트리의 노드와 그 자손 노드들로 구성됩니다. tree 역시 자체의 서브트리로 간주될 수 있습니다.

 

제한조건

• 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].
• -10^4 <= root.val <= 10^4
• -10^4 <= subRoot.val <= 10^4

 

입출력 예

입력	출력
root = [3,4,5,1,2], subRoot = [4,1,2]	true
root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]	false

 

 

해답 및 해설

파이썬 (Python)

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def isSame(p, q):
            if p and q:
                return p.val == q.val and isSame(p.left, q.left) and isSame(p.right, q.right)
            return not p and not q

        def isSub(origin, sub):
            if not origin:
                return False

            if origin.val == sub.val and isSame(origin, sub):
                return True
            
            return isSub(origin.left, sub) or isSub(origin.right, sub)
        
        return isSub(root, subRoot)

 

같은지 다른지는 이전 문제 같은 트리와 같은 코드를 이용하였다. 값이 같고 트리가 같은 트리인지 판별해서 맞으면 True, 값이 같지 않다면 재귀로 원래 트리의 하위트리와 비교하는 방식을 썼다. 트리 끝까지 내려가서 비교할 대상이 None으로 없으면 False가 뜨고, 그 전에 같은 트리가 있으면 True가 뜨게된다.