[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 리턴

 

 

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

 

 

---

 

 

 

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

 

 

 

---

 

 

 

탐색을 하는 도중에 subRoot 포인터를 수정하게 된다면 되돌리기 위해 복사본을 미리 만들어야 된다

이렇게 되면 매번 함수에 들어갈때 마다 이진 트리 하나를 계속해서 복사해야 되기 때문에 차라리 탐색이 낫다

 

1. 현재 Root 노드와 subRoot 노드의 값이 같은지 확인

2. 같다면 만들어 놓은 재귀 함수에 넣어 같은지 확인하고 True/False 리턴

3. 다시 돌아와 같지 않다면 계속해서 탐색 ↔ 같으면 True 리턴

 

 

class Solution:
    # 같은지 확인하기 위한 재귀 함수
    def checkSame(self, r, s):
        if not r and not s: # 둘다 None에 도달했으면 리턴
            return True
        
        if r and s and r.val == s.val: # 값이 같은지 확인하고 재귀로 왼,오 확인
            return self.checkSame(r.left, s.left) and self.checkSame(r.right, s.right)

        return False
    
    def isSubtree(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not subRoot: return True # 확인해야 되는 트리가 비어 있다면 이미 True
        if not root: return False # 비교할 트리가 없다면 False
        
        if self.checkSame(root, subRoot): # 현재 root와 subRoot의 root 가 같은지 확인
            return True

        return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot)

 

 

 

 

생각 보다 문제를 푸는데 잔 실수가 많아서 계속해서 프린트하고 뭐가 틀린지 확인 한것 같다

미리 생각을 하고 필요에 따라 종이에 적으면서 코드를 짜는 연습을 더 해야될 것 같다