[leetcode] 101. Symmetric Tree

원문)

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

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

문제접근)

1. 접근

• left자식노드와 right자식노드를 순회를 하는데
  right노드를 반대로 돌려서 순회하고 그 순회된 값을 가지고 비교

2. 접근

• 1접근과 비슷하지만, rev가 필요없는 방안이다.
  비교자체를 밖과 안의 노드들끼리 비교한다.
  리프노드는 True, 값이 다르거나 level이 다르면 False.

코드)

1. 접근

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return True l = self.top_down(root.left, False) r = self.top_down(root.right, True) return l == r def top_down(self, root: TreeNode, rev: bool): if root is None: return [None] tmp = [] tmp += [root.val] if rev: tmp += self.top_down(root.right, rev) tmp += self.top_down(root.left, rev) else: tmp += self.top_down(root.left, rev) tmp += self.top_down(root.right, rev) return tmp

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return True return self.traverse(root.left, False) == self.traverse(root.right, True) def traverse(self, root: TreeNode, rev: bool) -> List[int]: if root is None: return [] answer = [] stack = [root] while stack: cur = stack.pop() if cur: answer.append(cur.val) if rev: stack.append(cur.left) stack.append(cur.right) else: stack.append(cur.right) stack.append(cur.left) else: answer.append(cur) return answer

2. 접근

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

# Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def isSymmetric(self, root: TreeNode) -> bool: if root is None: return True return self.top_down(root.left, root.right) def top_down(self, left: TreeNode, right: TreeNode) -> bool: if left is None and right is None: return True elif left and right and left.val == right.val: _out = self.top_down(left.left, right.right) _in = self.top_down(left.right, right.left) return _in and _out else: return False

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        if root is None:
            return True
        
        stack = [(root.left, root.right)]
        ret = True
        
        while stack:
            left, right = stack.pop()
            
            if left is None and right is None:
                continue
            elif left and right and left.val == right.val:
                stack.append((left.left, right.right))
                stack.append((left.right, right.left))
            else:
                return False
        return True