106. Construct Binary Tree from Inorder and Postorder Traversal – Leetcode Solutions

Example 1:
Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

Example 2:

Input: inorder = [-1], postorder = [-1]
Output: [-1]

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # Create a dictionary to store the index of each value in the inorder array for quick access
        inorder_index_map = {val: idx for idx, val in enumerate(inorder)}
        
        # Define a recursive helper function to build the tree
        def helper(in_left, in_right):
            # If there are no elements to construct the subtree
            if in_left > in_right:
                return None
            
            # The last element in the current postorder list is the root of the current subtree
            val = postorder.pop()
            root = TreeNode(val)
            
            # Get the index of the root in the inorder array
            index = inorder_index_map[val]
            
            # Recursively build the right subtree
            root.right = helper(index + 1, in_right)
            # Recursively build the left subtree
            root.left = helper(in_left, index - 1)
            
            return root
        
        # Initialize the recursive function with the bounds of the inorder array
        return helper(0, len(inorder) - 1)

/**
 * @param {number[]} inorder
 * @param {number[]} postorder
 * @return {TreeNode}
 */
var buildTree = function(inorder, postorder) {
    // Create a map to store the index of each value in the inorder array for quick access
    const inorderIndexMap = {};
    inorder.forEach((val, index) => {
        inorderIndexMap[val] = index;
    });

    // Define a recursive helper function to build the tree
    function helper(inLeft, inRight) {
        // If there are no elements to construct the subtree
        if (inLeft > inRight) {
            return null;
        }

        // The last element in the current postorder array is the root of the current subtree
        const val = postorder.pop();
        const root = new TreeNode(val);

        // Get the index of the root in the inorder array
        const index = inorderIndexMap[val];

        // Recursively build the right subtree first because postorder processes right subtree before left subtree
        root.right = helper(index + 1, inRight);
        // Recursively build the left subtree
        root.left = helper(inLeft, index - 1);

        return root;
    }

    // Initialize the recursive function with the bounds of the inorder array
    return helper(0, inorder.length - 1);
};

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // Create a map to store the index of each value in the inorder array for quick access
        HashMap<Integer, Integer> inorderIndexMap = new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            inorderIndexMap.put(inorder[i], i);
        }
        
        // Initialize the postorder index to the last element
        int postorderIndex = postorder.length - 1;
        
        // Call the recursive helper function to construct the tree
        return buildTreeHelper(postorder, inorder, 0, inorder.length - 1, postorderIndex, inorderIndexMap);
    }
    
    private TreeNode buildTreeHelper(int[] postorder, int[] inorder, int inStart, int inEnd, int postIndex, HashMap<Integer, Integer> inorderIndexMap) {
        // Base case: if inStart is greater than inEnd, return null
        if (inStart > inEnd) {
            return null;
        }
        
        // Create a new TreeNode with the current root value from postorder
        TreeNode root = new TreeNode(postorder[postIndex]);
        
        // Find the index of the root value in inorder array using the map
        int inIndex = inorderIndexMap.get(root.val);
        
        // Recursive call to build the right subtree first because postorder processes right subtree before left subtree
        root.right = buildTreeHelper(postorder, inorder, inIndex + 1, inEnd, postIndex - 1, inorderIndexMap);
        // Recursive call to build the left subtree
        root.left = buildTreeHelper(postorder, inorder, inStart, inIndex - 1, postIndex - (inEnd - inIndex) - 1, inorderIndexMap);
        
        return root;
    }
}

public class Solution {
    public TreeNode BuildTree(int[] inorder, int[] postorder) {
        // Dictionary to hold the indices of inorder values for quick lookup
        Dictionary<int, int> inorderIndexMap = new Dictionary<int, int>();
        for (int i = 0; i < inorder.Length; i++) {
            inorderIndexMap[inorder[i]] = i;
        }
        
        // Helper function to build the tree recursively
        return BuildTreeHelper(inorder, 0, inorder.Length - 1, postorder, 0, postorder.Length - 1, inorderIndexMap);
    }
    
    private TreeNode BuildTreeHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, Dictionary<int, int> inorderIndexMap) {
        // Base case
        if (inStart > inEnd || postStart > postEnd) {
            return null;
        }
        
        // The last element of postorder is the root
        int rootVal = postorder[postEnd];
        TreeNode root = new TreeNode(rootVal);
        
        // Root index in inorder array
        int inorderRootIndex = inorderIndexMap[rootVal];
        
        // Numbers of nodes in left subtree
        int leftTreeSize = inorderRootIndex - inStart;
        
        // Recursively build the left and right subtrees
        root.left = BuildTreeHelper(inorder, inStart, inorderRootIndex - 1, postorder, postStart, postStart + leftTreeSize - 1, inorderIndexMap);
        root.right = BuildTreeHelper(inorder, inorderRootIndex + 1, inEnd, postorder, postStart + leftTreeSize, postEnd - 1, inorderIndexMap);
        
        return root;
    }
}