45. Invert Binary Tree

🎯 leetcode - 226. Invert Binary Tree

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 45번 문제

📌 날짜

2020.02.16

📌 시도 횟수

5 try

💡 Code

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        queue = [root]
        while queue:
            node = queue.pop(0)
            if node:
                node.left, node.right = node.right, node.left
                queue.append(node.left)
                queue.append(node.right)
        return root

💡 문제 해결 방법

- BFS를 이용해서 이진 트리의 상위 노드부터 뒤집었다.
- 뒤집는 과정을 나타내면 다음과 같다.

1. 처음 상태
     4
   /   \
  2     7
 / \   / \
1   3 6   9

2. node = 4
     4
   /   \
  7     2	<< node.left, node.right = node.right, node.left
 / \   / \
6   9 1   3

3. node = 7, 2
     4
   /   \
  7     2
 / \   / \
9   6 3   1	<< node.left, node.right = node.right, node.left

3. node = 9, 6, 3, 1 (*node.left, node.right가 모두 None이라서 바뀌는 것이 없음)
     4
   /   \
  7     2
 / \   / \
9   6 3   1

💡 새롭게 알게 된 점

-

❌ (한번에 맞추지 못한 경우) 오답의 원인

✔ if node: 조건을 추가해주지 않아서 에러가 생겼다.
- 위의 코드에서는 리프노드 이후의 None 값까지 queue에 담는다.
None에 대해서는 node.left, node.right를 구할 수 없다.
따라서 무조건 if node: 라는 조건문을 추가해주어야 한다~!

---

😉 다른 풀이

📌 하나. 간결한 풀이

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return None
        root.left, root.right = \
            self.invertTree(root.right), self.invertTree(root.left)
        return root

💡 문제 해결 방법

- 재귀를 통해 리프노드까지 내려가서 백트래킹 하면서 스왑하는 상향 방식
- 위의 BFS를 통한 풀이와 스왑 방향이 반대이다. (리프부터 스왑 ~ 루트로 이동)

---

📌 둘. DFS + 반복구조

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        stack = [root]
        while stack:
            node = stack.pop()
            if node:
                node.left, node.right = node.right, node.left
                stack.append(node.left)
                stack.append(node.right)
        return root

💡 문제 해결 방법

- queue.pop(0)을 stack.pop()으로 수정하여
LIFO를 따르는 stack으로 바꿈으로써 DFS로 구현했다.
- DFS의 pop 순서(4>2>1>3>7>6>9)대로 차례대로 left, right를 스왑한다.

---