[Leetcode] 101. Symmetric Tree

문제 바로가기

기본 풀이 방식은 동일하나 Recursion이 Loop보다 거의 두배 빨랐다. 이는 list의 잦은 추가와 삭제에서 오는 차이때문으로 생각된다.

Loop

Time Complexity: $O(n)$
Space Complexity: $O(\log n)$

# 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 isSymmetric(self, root: TreeNode) -> bool:
        stack = [(root.left, root.right)]
        
        while stack:
            leftTop, rightTop = stack.pop()
            if leftTop is None and rightTop is None:
                continue
            if leftTop is None or rightTop is None:
                return False
            if leftTop.val != rightTop.val:
                return False    
            stack.append((leftTop.left, rightTop.right))
            stack.append((leftTop.right, rightTop.left))
        return True

Recursion

Time Complexity: $O(n)$
Space Complexity: $O(\log n)$

# 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 isSymmetric(self, root: TreeNode) -> bool:
        def symmetric_helper(root1, root2):
            if root1 is None and root2 is None:
                return True
            if root1 is None or root2 is None:
                return False
            if (root1.val == root2.val and 
                symmetric_helper(root1.right, root2.left) and 
                symmetric_helper(root1.left, root2.right)):
                return True
            return False
        
        return symmetric_helper(root.left, root.right)