[LeetCode] 226 | Invert Binary Tree

226 | Invert Binary Tree
https://leetcode.com/problems/invert-binary-tree/

 

 

 

 

이상 코드

 

 

재귀함수를 이용한 풀이

 

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

 

 

• 재귀 함수로 작성
• root.right 를 인자를 넘겼기 때문에 맨 오른쪽의 리프 노드부터 스왑이 이루어짐
• 가장 말단, 리프 노드까지 내려가서 백트래킹하면서 스왑하는 상향 (Bottom-Up) 방식

 

 

BFS를 이용한 풀이

 

class Solution:
    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

 

 

• 부모 노드부터 스왑하면서 아래로 내려가는 하향 (Top-Down) 방식 풀이 

 

 

 

DFS를 이용한 풀이

 

class Solution:
    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

 

 

• popleft() 를 pop() 으로 수정