[LEET CODE] 226. Invert Binary Tree

# Problem

Given the root of a binary tree, invert the tree, and return its root. Constraints: The number of nodes in the tree is in the range [0, 100]. -100 <= Node.val <= 100

 

# My Answer

class Solution:
    def invertTree(self, root: TreeNode) -> TreeNode:
        def invert(tree):
            if tree is None:
                return tree
                
            if tree.left:
                node = tree.left  # node에 임시 저장 
            else:
                node = None
                
            if tree.right: 
                tree.left = invert(tree.right) # left에 원래 right 붙여주기
            else:
                tree.left = None # right가 없으니 invert 하면 left가 None이 됨
                
            tree.right = invert(node) # node에 저장해 두었던 원래 left 붙이기
            
            return tree
            
        return invert(root)

 

# Solution 1 - 파이썬다운 방식

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

return None은 생략가능 ( 파이썬은 자동으로 None 리턴 ) 

 

# Solution 2 - 반복구조로 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

 

# Solution 3 - 반복구조로 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

 

# Solution 4 - 반복구조로 DFS 후위 순회

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

탐색 순서만 변화