LC 105 & LC 106 & LC 654

Solution to LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal, LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal, and LeetCode 654 Maximum Binary Tree.

LeetCode 105

Construct Binary Tree from Preorder and Inorder Traversal. (Medium) [link]

Recursive solution.

Recursion termination criteria: if preorder tree is None, return None. The first node of preorder tree is the current middle node. This is how we find the level order nodes.

Find the separation point and use it to slice inorder tree and preorder tree. Note that the size of the left part of inorder tree is the same of the size of the right part of the preorder tree, same as the right part. Keep left inclusive right exclusive rule. Resursion on the left part of the inorder and preorder tree and also on the right part of the inorder and preorder tree.

Note that to construct a tree, we only need to make sure every left child and right child correspond to the correct parent node.

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder:
            return None

        cur_val = preorder[0]
        root = TreeNode(cur_val)

        separator = inorder.index(cur_val)
        inorder_left = inorder[:separator]
        inorder_right = inorder[separator+1:]

        preorder_left = preorder[1:len(inorder_left)+1]
        preorder_right = preorder[len(inorder_left)+1:]

        root.left = self.buildTree(preorder_left, inorder_left)
        root.right = self.buildTree(preorder_right, inorder_right)
        
        return root

LeetCode 106

Construct Binary Tree from Inorder and Postorder Traversal. (Medium) [link]

Recursive solution.

Recursion termination criteria: if postorder tree is None, return None. The final node of postorder tree is the current middle node. This is how we find the level order nodes.

Find the separation point and use it to slice inorder tree and postorder tree. Note that the size of the left part of inorder tree is the same of the size of the right part of the postorder tree, same as the right part. Keep left inclusive right exclusive rule. Resursion on the left part of the inorder and postorder tree and also on the right part of the inorder and postorder tree.

# 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 buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        if not postorder:
            return None
        root_val = postorder[-1]
        root = TreeNode(root_val)

        separator = inorder.index(root_val)

        inorder_left = inorder[:separator]
        inorder_right = inorder[separator+1:]

        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left): len(postorder)-1]

        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)
        return root

LeetCode 654

Maximum Binary Tree (Medium) [link]

# 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 constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        if not nums:
            return None
        
        cur_val = max(nums)
        root = TreeNode(cur_val)

        separator = nums.index(cur_val)
        
        left = nums[:separator]
        right = nums[separator+1:]

        root.left = self.constructMaximumBinaryTree(left)
        root.right = self.constructMaximumBinaryTree(right)

        return root