# Leetcode :: Symmetric Tree

wisepine·2021년 5월 25일
0

## 알고리즘

목록 보기
99/121

### Problem

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

### Guess

• recursive, iterative 모두 적용해보자.
• 두 subtree 각각 left과 right, right과 left을 비교해주면 되겠다.

### 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
배운거 아카이빙하는 곳