[leetcode] subtree-of-another-tree.py

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

Subtree of Another Tree - LeetCode

 

subRoot 노드가 root 노드의 subtree인지 확인하는 문제입니다.

노드의 val, left, right가 같은지 확인하면서 들어가야해서 두개의 재귀함수가 필요했습니다.

None처리가 굉장히 복잡했던 문제..

dfs함수는 root함수를 dfs로 탐색하고, compare_tree는 하나씩 들어갈때마다 노드가 같은지 확인하는 함수입니다.

 

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def compare_tree(a, b):
            if a is None and b is None:
                return True
            # 둘 중 하나만 None이면  False
            if (a is None or b is None) or a.val != b.val:
                return False
            # left, right 둘 다 같을경우  True
            return compare_tree(a.left, b.left) and compare_tree(a.right, b.right)
            
        def dfs(node, subRoot):
            if compare_tree(node, subRoot):
                return True
            if node:
                return dfs(node.left, subRoot) or dfs(node.right, subRoot)
            # 둘 다 None인경우 True
            return node == subRoot
        
        return dfs(root, subRoot)