[leetcode] 226. 이진 트리 반전 (Invert Binary Tree)

들어가며

본 포스팅은 <파이썬 알고리즘 인터뷰> 책에서 다룬 리트코드 문제들을 다루고 있습니다. 

문제들은 모두 리트코드에서 출제된 문제들이며, 문제 풀이의 많은 부분을 책의 힌트와 해설을 참고하였습니다. 

 

포스팅되는 모든 문제들의 목록과 풀이는 파이썬 알고리즘 인터뷰에서 제공하는 깃허브에서 확인하실 수 있습니다.

 

---

문제

Given the root of a binary tree, invert the tree, and return its root.

 

주어진 이진트리를 반전시켜 루트를 리턴하라.

 

 

입출력 예시

Example 1:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

 

 

생각과정

간단하게 노드를 하나씩 써내온 다음 그 노드의 left와 right를 스왑시켜 다시 집어넣어주면 해결된다.

 

 

풀이

def invertTree(lst):
    queue = collections.deque([lst])

    while queue:
        node = queue.popleft()
        if node:
            node.left, node.right = node.right, node.left

            queue.append(node.left)
            queue.append(node.right)

    return lst

 

BFS를 이용한 방식으로, 크게 어렵지 않아 아이디어만 제대로 생각해낸다면 금방 해결할 수 있다.

 

처음에 root를 담는 데크를 생성한 후, 데크를 while으로 돌면서 lst의 노드 하나씩을 꺼내온다.

꺼내온 노드는 left와 right를 가지고 있을텐데, 이걸 스왑해주고, 스왑된 노드를 각각 왼쪽가 오른쪽에 넣어준다.

 

그럼 다음 while문에서 꺼내오는 노드는 스왑이 된 원래의 오른쪽 노드, 입력 예시 1에서 봤을 때 7이 스왑된 노드이다.

 

계속 while문을 돌면서 같은 과정을 반복하면, 자식 노드가 없는 부모노드가 pop되었을 때는 None이 append되므로 결국 if문을 타지 못하게 되고, 마지막에 while문이 끝나면 반전된 트리가 리턴된다. 

 

---

마치며

계속해서 BFS방식으로 된 코드가 나오니 점점 눈에 익는 것 같다. 반복학습 최고!!