[leetcode] 101. Symmetric Tree

leetcode 100.same tree가 자식 노드가 같은지를 판단하는 것이었다면, 

이 문제는 left child가 right child와 같은지 보면 된다.

 

대칭인지 확인하기 위해서는 left subtree와 right subtree를 가지고 동시에 dfs를 돌려야 한다.

 

시간 복잡도는 O(n)이다. 여기서 n은 the number of node.

메모리 복잡도는 O(h)이고, h는 height of a tree.

 

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        
        def dfs(left, right):
            if not left and not right:
                return True
            if not left or not right:
                return False
            return ((left.val == right.val) and 
           dfs(left.left, right.right) and dfs(left.right, right.left))

        return dfs(root.left, root.right)