LC 226 & LC 106

Recursion Queue
Binary Tree
Publish Date:   2022-05-25

Solution to LeetCode 226 Invert Binary Tree and LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal.

LeetCode 226

Invert Binary Tree (Easy) [link]

1] Recursive solution. Pre-order traversal.

# 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 not root:
            return None
        root.left, root.right = root.right, root.left

        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

2] Iterative solution. Pre-order traversal.

# 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 not root:
            return None
        que = deque([root])
        while que:

            node = que.popleft()
            node.left, node.right = node.right, node.left
            if node.left:
                que.append(node.left)
            if node.right:
                que.append(node.right)
        return root

3] Iterative solution. Breadth first search. Level-order traversal.

# 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 not root:
            return None
        que = deque([root])
        while que:
            size = len(que)

            for i in range(size):
                node = que.popleft()
                node.left, node.right = node.right, node.left
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
        return root

LeetCode 106

Construct Binary Tree from Inorder and Postorder Traversal

Recursion Queue
  TOC