[LeetCode] 226. Invert Binary Tree

1. 문제 이해

이진 트리를 반전시키는 문제다.

반전시킨 뒤, root 노드를 리턴한다.

 

 

2. 풀이 과정

큐를 이용한 반복 구조로 BFS 알고리즘을 구현한다.

 

처음 구현한 코드는 다음과 같다.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return

        queue = collections.deque([root])
       
        while queue:
            for _ in range(len(queue)):
                cur = queue.popleft()
                
                cur.left, cur.right = cur.right, cur.left

                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)    
        
        return root

이 코드는 이진 트리를 레벨(층) 단위로 반전시키는 것이다.

하지만 이 문제에서는 레벨 단위로 수행하는 일이 없다. 따라서 len(queue) 부분은 불필요한 반복문이다.

 

코드를 다음과 같이 수정한다.

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return

        queue = collections.deque([root])
       
        while queue:
            cur = queue.popleft()
            if cur:
                cur.left, cur.right = cur.right, cur.left
                queue.append(cur.left)
                queue.append(cur.right)
        
        return root

큐에 None이 추가될 수 있기 때문에 "if cur:" 구문을 추가한다. 

 

3. 전체 코드

class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if root is None:
            return

        queue = collections.deque([root])
       
        while queue:
            cur = queue.popleft()
            if cur:
                cur.left, cur.right = cur.right, cur.left
                queue.append(cur.left)
                queue.append(cur.right)
        
        return root

 

 

4. 생각할 점

- 불필요한 반복문이 있는지 항상 생각한다. 모든 코드는 문제 풀이와 연관되어야 한다.

 

 

5. 출처

- https://leetcode.com/problems/invert-binary-tree/

- 박상길, 파이썬 알고리즘 인터뷰, 책만, 2020