[LeetCode/Python] 226.이진 트리 반전(Invert Binary Tree)

 

 

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

 

 

 

Example

 

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

 

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

 

 

 

1. 파이썬다운 방식

 

 

# 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]:
        if root:
            root.left, root.right = self.invertTree(root.right), self.invertTree(root.left)
            return root
        return None

 

해설

 

재귀 구조로 쉽게 해결할 수 있다.

 

재귀 진행 순서

 

코드 상으로 self.invertTree(root.right)가 먼저 시작하므로

 

최종 아랫단에서는 "9"에서 시작한다.

 

참고로 마지막 return None은 생략이 가능하다.

 

파이썬에서는 아무것도 리턴하지 않으면 자연스럽게 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

 

해설

 

흐름

 

위에서 아래로 내려가면서 스왑하는 코드이다.

 

(너비 우선 탐색)

 

deque를 사용하였고 root의 경우 값을 참조하였으므로

 

최종적으로 root를 리턴하면 된다.

 

 

 

 

3. 반복 구조로 DFS

 

 

# 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]:
        stack = collections.deque([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

 

해설

 

흐름

 

2번 코드에서 바뀐 거라곤 popleft와 pop의 차이 정도?

 

하지만 진행 순서는 확연히 다르다.

 

이 코드는 깊이 우선 탐색이 된다.

 

 

 

 

 

4. 반복 구조로 DFS 후위 순회

 

 

# 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]:
        stack = collections.deque([root])
        
        while stack:
            node = stack.pop()
 
            if node:
                stack.append(node.left)
                stack.append(node.right)
 
                node.left, node.right = node.right, node.left # 후위 순회
                
        return root

 

해설

 

3번 코드에서 stack에 추가해주는 단계를 먼저 진행했을 뿐이다.

 

이렇게 바꾸면 전위 순회였던 3번 코드에서 후위 순회로 변경되는 것인데

 

사실 아직 부족해서 이게 왜 후위 순회인지 모르겠다.

 

나중에 알게되면 추가하겠다.

 

댓글로 알려주시면 ㄳ

 

 

※ 전위 순회

 

뿌리를 먼저 방문하는 방식

 

 

※ 후위 순회

 

하위 트리를 모두 방문 후 뿌리를 방문하는 방식