101. Symmetric Tree - python3

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

    1
   / \
  2   2
   \   \
   3    3

우선 너비 우선 순회의 아이디어를 생각

# 너비 우선 순회(BFS)
    def level_order_traversal(self, root):
        def _level_order_traversal(root):
            queue = [root]
            while queue:
                root = queue.pop(0)
                if root is not None:
                    print(root.val)
                    if root.left:
                        queue.append(root.left)
                    if root.right:
                        queue.append(root.right)
        _level_order_traversal(root)

근데 모르겠음...; 동지들아 Help ~~

My Answer 1: Accepted (Runtime: 36 ms / Memory Usage: 14.2 MB)

# 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:
        if not root:
            return True
        
        # root의 left, right를 넣기
        queue = [(root.left, root.right)]

        while queue:
            # left는 l로, right는 r로 pop
            l,r = queue.pop()
            
            # 둘다 null 이면 같으니까 continue
            if not l and not r:
                continue
            # 둘중에 하나만 null 이면 다르니까 False
            if not l or not r:
                return False
            # 둘이 값이 다르면 False
            if l.val != r.val:
                return False
            
            # 대칭이어야 하는 애들끼리 append
            queue.append((l.left, r.right))
            queue.append((r.left, l.right))
            
        return True

동지들의 도움을 받아 (left, right) 를 한 세트로 다루는 방식을 이용
이러면 대칭으로 비교를 한다

Other Answer 1: (Runtime: 36 ms / Memory Usage: 14.3 MB)

# Recursion
    def isSymmetric(self, root: TreeNode) -> bool:
        if not root:
            return True
        return self.dfs(root.left, root.right)
    
    def dfs(self, p, q):
        if not p and not q:
            return True
        if None in [p,q]:
            return False
        if p.val == q.val:
            return self.dfs(p.right, q.left) and self.dfs(p.left, q.right)

이건 재귀를 이용한 방식
iterative 와 유사한 방식이고 런타임이나 메모리 사용도 비슷하다.

트리 공부가 필요할듯^^;