[알고리즘] Leetcode #226 이진 트리 반전 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

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: []

 

Constraints

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

 

Code

# 반복 구조로 BFS
def invertTree(self, root: TreeNode) -> TreeNode:
    queue = collections.deque([root])
    
    while queue:
        node = queue.popleft()
        # 부모 노드부터 하향식 스왑
        if node:
            node.left, node.right = node.right, node.left
            
            queue.append(node.left)
            queue.append(node.right)
        
    return root

트리를 뒤집기 위해 선입선출의 큐를 만들어 트리노드 자료를 저장해둔다. 이후, 큐의 popleft() 기능을 이용해 부모노드 (가장 왼쪽 값)부터 right, left의 자식노드를 바꿔준다. 이렇게 맨 아래 리프노드까지 자식노드들을 바꿔주면 전체 트리가 반전된다. (마지막 노드는 자식노드로 None 반환 -> if문 해당 x)