[Leetcode 아주 상세한 문제풀이] 572. Subtree of Another Tree – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 572번 문제 Subtree of Another Tree 다.

우선 문제를 살펴보자.

 

리트코드 572번 문제 Subtree of Another Tree 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

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

 

 

문제 설명

문제를 간략히 살펴보자. 인풋으로 두 개의 binary tree가 주어진다. 하나는 root를 기준으로 하는 binary tree고 또 하나는 subroot를 기준으로 하는 binary tree다. 이때 subroot를 기준으로 하는 binary tree가 root를 기준으로 하는 binary에 '같은 구조'로 속하는지 판단하라는 문제다.

문제 예시 1번의 경우 root를 기준으로 하는 binary tree로 [3,4,5,1,2], subroot를 기준으로 하는 binary tree로 [4,1,2]가 주어졌다. 이때 subroot를 기준으로 하는 binary tree [4, 1, 2]는 root를 기준으로 하는 binary tree의 왼쪽 subtree에 속한다. 이때 추가 sub-subtree 없이 동일한 구조로 속하기 때문에 이 경우 true를 리턴하면 된다. 문제를 이해하는데 어렵지 않기 때문에 곧바로 문제를 풀어보도록 하자.

 

 

문제 접근법

이 문제를 해결하기 위하여 우리는 두 개의 함수를 만들어 줄 것이다.

첫 번째 함수

 

첫번째 함수는 두 개의 binary tree가 같은지 판단하는 함수다.

두 개의 노드 (p and q)를 입력받아 그것들이 각 binary tree의 root인지 확인하다.

우리는 이 함수를 재귀적으로 사용하여 binary tree를 탐색한 것인데 여기서 몇 가지 경우의 수가 생기게 된다.

1) p와 q가 모두 none인 경우

이 경우 우리는 tree의 마지막에 '동시에' 도달했음을 알 수 있다. 따라서 이 경우 마지막 부분은 같으므로 true를 리턴한다.

2) p와 q가 다른경우

p와 q가 다르거나 혹은 둘 중 하나는 none이고 또 다른 하나는 특정 값을 가질 경우가 있다. 이 경우 비교하는 두 개의 tree는 서로 다르므로 false를 리턴한다.

3) 그 외의 경우

위 두 가지 경우를 제외한 경우 재귀함수를 이용해 탐색을 계속 한다. root를 기준으로 왼쪽과 오른쪽 child를 모두 비교해야 하며 이 둘이 모두 같아야 true를 리턴한다. 따라서 이 경우 AND 로직을 사용해야 한다.

 

두 번째 함수

두 번째 함수는 subroot가 root의 subtree에 해당하는지 판단하는 함수다.

이 함수는 다음과 같이 작동한다.

1) subroot가 none인 경우

이 경우 어떤 tree든 subtree로 취급될 수 있다. 따라서 이 경우 true를 리턴한다. 만약 root는 none인데 subroot가 none이 아니라면 이 얘기는 subroot가 root의 subtree가 아니란 뜻이므로 false를 리턴한다.

2) 현재 탐색 노드를 root로 하는 tree가 subroot를 기준으로 하는 tree와 같은지 판단한다. 만약 그 둘이 같다면 true를 리턴한다.

3) 만약 위 경우에서 그 둘이 다르다면 우리는 재귀함수를 이용하여 왼쪽과 오른쪽 child 노드들을 탐색한다. 만약 그 둘 중 하나라도 true를 리턴한다면 그곳에 subroot를 기준으로 하는 tree가 있다는 뜻이므로 true를 리턴한다.

설명이 조금 복잡할 수 있는데 코드를 보면 더 명확히 이해할 수 있을 것이다.

이제 코드를 한 번 살펴보자.

 

 

문제 풀이

Binary tree를 표현하기 위한 class를 선언해준다. (line 1-5)

이는 파이썬에서 일반적으로 사용되는 표현식이니 익숙해 지도록 하자.

먼저 두 개의 노드 (p and q)를 입력받아 그것들이 각 binary tree의 root인지 확인하는 함수를 정의해 준다. (line 7)

만약 p와 q 모두 none 이라면 tree의 마지막에 '동시에' 도착한 것이므로 true를 리턴해준다. (line 8-9)

만약 p와 q중 하나가 none이거나 혹은 p와 q가 다를 경우 비교하는 binary tree가 다른 것이므로 flase를 리턴해준다. (line 10-11)

위 두 가지 경우가 아니라면 이 함수를 재귀적으로 불러와 탐색을 계속한다. (line 12)

이때 유의할 점은 우리는 subtree 전체를 비교하고 있으므로 root를 기준으로 왼쪽과 오른쪽 모두 탐색을 진행해야 하며 왼쪽 오른쪽 모두 true를 리턴할 때 같은 binary tree임을 잊지 말자.

두번째로 subroot가 root의 subtree에 해당하는지 판단하는 함수다. (line 14)

만약 subroot가 none 이라면 어떤 tree든 subtree로 취급될 수 있으므로 true를 리턴해준다. (ine 15-16)

혹시 root는 none인데 subroot가 none이 아니라면 이 얘기는 subroot가 root의 subtree가 아니란 뜻이므로 false를 리턴해준다. (line 17-18)

그리고 현재 탐색 노드를 root로 하는 tree가 subroot를 기준으로 하는 tree와 같은지 판단한다.

만약 그 둘이 같다면 true를 리턴한다. (line 19-20)

이 과정 역시 재귀적으로 진행해야 하는데 root를 기준으로 왼쪽과 오른쪽 모두 탐색을 해야 한다. (line 21)

하지만 이 경우 우리는 subroot가 root의 subtree에 속하는지 판단하고 있으므로 왼쪽이든 오른쪽이든 한 곳에만 있으면 된다.

따라서 재귀함수를 이용해 왼족과 오른쪽을 탐색하되 OR 연산자를 이용해 결과를 리턴한다. (line 21)

 

 

문제 풀이 코드

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def isSameTree(p, q):
    if not p and not q:
        return True
    if not p or not q or p.val != q.val:
        return False
    return isSameTree(p.left, q.left) and isSameTree(p.right, q.right)
 
def isSubtree(root, subRoot):
    if not subRoot:
        return True
    if not root:
        return False
    if isSameTree(root, subRoot):
        return True
    return isSubtree(root.left, subRoot) or isSubtree(root.right, subRoot)
 
# Example usage
# Construct the trees as per the example
# root = [3,4,5,1,2], subRoot = [4,1,2]
root = TreeNode(3)
root.left = TreeNode(4)
root.right = TreeNode(5)
root.left.left = TreeNode(1)
root.left.right = TreeNode(2)
 
subRoot = TreeNode(4)
subRoot.left = TreeNode(1)
subRoot.right = TreeNode(2)
 
print(isSubtree(root, subRoot))  # Output: True
 

 

 

관련 문제

리트코드 98번 Validate binary search tree 문제 풀이 (링크)

리트코드 102번 Binary tree level order traversal 문제 풀이 (링크)

리트코드 104번 Maximum depth of binary tree 문제 풀이 (링크)

리트코드 105번 Construct binary tree from preoder and inorder traversal 문제 풀이 (링크)

리트코드 124번 Binary tree maximum path sum 문제 풀이 (링크)

리트코드 208번 Implement tree (Prefix tree) 문제 풀이 (링크)

리트코드 212번 Word search 2 문제 풀이 (링크)

리트코드 226번 Invert/flip binary tree 문제 풀이 (링크)

 

572. Subtree of Another Tree