[파이썬 알고리즘]226.leetcode - 이진 트리 반전

문제 말 그대로 이진 트리를 반전하는 문제이다.

 

풀이 1) 반복 구조로 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

 

풀이 2) 반복 구조로 DFS

def invertTree(self, root: TreeNode) -> 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

 

풀이 3) 반복 구조로 DFS 후위 순회

def invertTree(self, root: TreeNode) -> 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