[Leetcode/Python] Symmetric Tree

Top Interview Questions 의 Easy Collection에 있는 문제입니다.       
문제는 여기서 볼 수 있습니다.

 

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

 

Example 1:

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

Input: root = [1,2,2,null,3,null,3]
Output: false

 

Constraints:

• The number of nodes in the tree is in the range [1, 1000].
• -100 <= Node.val <= 100

 

Follow up: Could you solve it both recursively and iteratively?

 

Code:

from typing import Optional


# 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

# stack을 활용한 풀이 : 검토할 양쪽 노드를 append -> 이후 pop하여 검토
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        if not root: return True
        stack = [(root.left, root.right)]
        
        while stack:
            cur = stack.pop()
            l, r = cur[0], cur[1]
            if not l and not r: continue
            if not l and r or not r and l or l.val != r.val: return False # OR조건 3가지임 유의하기
            stack.append((l.right, r.left))
            stack.append((l.left, r.right))
        
        return True

# 위의 풀이를 함수화해 간추림 : stack사용 안하고 재귀로 풀이
class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def helper(left, right):
            if not left and not right: return True
            if not left or not right or left.val != right.val: return False
            return helper(left.left, right.right) and helper(left.right, right.left)
        
        return helper(root.left, root.right)

 

설명은 위 코드에 주석으로 적혀 있다.

연결 리스트와 트리 문제가 약한 것 같다. 집중적으로 풀어야겠다...!