이진트리 반전

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

Invert Binary Tree - LeetCode

 

 1. 파이썬 다운 방식 

이 문제는 재귀를 통해 파이썬다운 방식으로 정말 쉽게 풀 수 있다. 그러나 막상 설명은 쉽지 않다.

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

 전체 코드에서 self.invertTree의 파라미터로 root.right를 먼저 넘겼기때문에 노드 오른쪽부터 재귀 탐색을 진행한다. root=7인 상태에서 노드 9에서 첫 번째 스왑이 일어나고(실제로는 그 자식인 None까지 탐색하다가 None을 리턴받은 후에), 두 번째는 노드 6에서 스왑이 일어난다.

 

 참고로 마지막 return None은 생략이 가능하다. 아무것도 리턴하지 않으면 자바나 C++는 당연히 에러를 내뱉겠지만 파이썬은 자연스럽게 None을 할당하기 때문이다.

 

 2. 반복 구조로 BFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[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

 먼저 삽입된 노드는 반복 구조로 계속 스왑되면서 자식 노드가 계속해서 큐에 추가되는 구조가 된다.

 

 앞서 재귀 풀이가 가장 말단, 리프 노드까지 내려가서 백트래킹하면서 스왑하는 상향 방식이라면, 이 풀이는 부모 노드부터 스왑하면서 계속 아래로 내려가는 하향 방식 풀이라 할 수 있다.