Tree: 572. Subtree of Another Tree

572. Subtree of Another Tree

 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        
        def sameTree(n1, n2):
            if not n1 and not n2: # 둘다 없으면
                return True
            if not n1 or not n2: # 둘중 하나만 없으면
                return False            
            if n1.val != n2.val: # 값이 다르면
                return False            
            return sameTree(n1.left, n2.left) and sameTree(n1.right, n2.right) # 두개가 좌우 트리가 같으면 True

        res = []
        def dfs(node):            
            if node.left:
                dfs(node.left)
            res.append(sameTree(node, subRoot))
            if node.right:
                dfs(node.right)

        dfs(root)

        return True if True in res else False

 

문제점

1. res 리스트 사용의 비효율성:
   • res 리스트에 값을 추가하고 나중에 True in res로 결과를 확인하는 것은 불필요합니다.
   • 대신, 트리를 탐색하며 sameTree가 True를 반환하면 즉시 결과를 반환하도록 할 수 있습니다.
2. DFS 구현 방식:
   • DFS 함수가 불필요하게 왼쪽과 오른쪽 자식 노드를 재귀적으로 탐색하고 나서 sameTree를 호출하는 구조입니다.
   • sameTree 호출과 DFS 탐색을 더 효율적으로 결합할 수 있습니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:        
        
        def sameTree(n1, n2):
            if not n1 and not n2: # 둘다 없으면
                return True
            if not n1 or not n2: # 둘중 하나만 없으면
                return False            
            if n1.val != n2.val: # 값이 다르면
                return False            
            return sameTree(n1.left, n2.left) and sameTree(n1.right, n2.right) # 두개가 좌우 트리가 같으면 True

        def dfs(node):            
            if not node:
                return False

            # 현재 노드가 서브노드랑 같은지 확인
            if sameTree(node, subRoot): # 같다고 나오면
                return True

            # 아니면, 좌우 체크한거 리턴
            return dfs(node.left) or dfs(node.right) # 둘 중 하나라도 true 나오면 true 리턴 될 것임

        return dfs(root)

 

 

https://youtu.be/E36O5SWp-LE

 

더 최적화

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:        
        if not subRoot: # 서브트리 없으면, 
            return True
        if not root: # 루트 없으면
            return False    
        
        def sameTree(n1, n2):
            if not n1 and not n2: # 둘다 없으면
                return True
            if not n1 or not n2: # 둘중 하나만 없으면
                return False            
            if n1.val != n2.val: # 값이 다르면
                return False            
            return sameTree(n1.left, n2.left) and sameTree(n1.right, n2.right) # 두개가 좌우 트리가 같으면 True

        if sameTree(root, subRoot): # 현재 노드가 서브노드랑 같은지 확인
            return True

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