[코테] 리트코드 트리 226. Invert Binary Tree

226. Invert Binary Tree

문제 링크

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

문제 설명

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

제한 사항

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

입출력 예 #1

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

입출력 예 #2

1. Input : root = [2,1,3]
2. Output : [2,3,1]

입출력 예 #3

1. Input : root = []
2. Output : []

문제 풀이

1. 파이썬의 재귀를 이용한 풀이 방법
2. 반복 구조로 BFS 기법 사용
3. 반복 구조로 DFS 기법 사용
4. 반복 구조로 DFS 후위 순회

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

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

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

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