Leetcode::Symmetric Tree


Problem


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

Guess

  • 再帰、反復はすべて適用される.
  • の2つのサブツリーは、それぞれ左、右、右、左を比較すればよい.
  • Sol 1. Recursive

    # 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 helper(self, p, q):
            if not p and not q: return True
            if not p or not q: return False
            if p.val != q.val: return False
            
            return self.helper(p.left, q.right) and self.helper(p.right, q.left)
            
            
        def isSymmetric(self, root: TreeNode) -> bool:
            return self.helper(root.left, root.right)

    Sol 2. Iterative

    from collections import deque
    
    class Solution:
        def check(self, p, q):
            if not p and not q: return True
            if not p or not q: return False
            if p.val != q.val: return False
            return True
        
        def isSymmetric(self, root: TreeNode) -> bool:
            dq = deque([(root.left, root.right)])
            
            while dq:
                p,q = dq.popleft()
                
                if not self.check(p,q):
                    return False
                
                if p:
                    dq.append((p.left, q.right))
                    dq.append((p.right, q.left))
                    
            return True