Construct Binary Tree from Inorder and Postorder Traversal

1. The main function buildTree initializes the process by calling a recursive helper function with the full range of both inorder and postorder arrays.
2. The recursive helper function buildHelper(inorder, inStart, inEnd, postorder, postStart, postEnd) works on the subarrays defined by the start and end indices.
3. Base Case: If the start index is greater than the end index for either array, it means the subarray is empty, and we return null.
4. Identify Root: The root of the current subtree is always the last element of the current postorder subarray (postorder[postEnd]). A new TreeNode is created with this value.
5. Find Root in Inorder: A linear search is performed on the current inorder subarray (from inStart to inEnd) to find the index of the root's value. Let's call this rootIndex.
6. Partition Subtrees:
   • The elements to the left of rootIndex in the inorder array (inStart to rootIndex - 1) belong to the left subtree.
   • The elements to the right of rootIndex (rootIndex + 1 to inEnd) belong to the right subtree.
7. Calculate Left Subtree Size: The number of nodes in the left subtree is calculated as leftSubtreeSize = rootIndex - inStart.
8. Recursive Calls:
   • The left child is constructed by a recursive call with the corresponding inorder and postorder subarrays for the left subtree.
   • The right child is constructed similarly with the subarrays for the right subtree.
9. Return Node: The constructed node with its left and right children attached is returned.

The algorithm is implemented using a recursive helper function that takes the start and end indices for the current segments of the inorder and postorder arrays. In each call, we first identify the root from the end of the postorder segment. Then, we iterate through the inorder segment to locate this root. This location tells us the boundary between the left and right subtrees. We can also determine the size of the left subtree, which helps in partitioning the postorder array for the subsequent recursive calls. The function then recursively calls itself to build the left and right children and connects them to the root.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public TreeNode buildTree(int[] inorder, int[] postorder) {18        if (inorder == null || postorder == null || inorder.length == 0) {19            return null;20        }21        return buildHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);22    }23 24    private TreeNode buildHelper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd) {25        // Base case: if the subarray is empty26        if (inStart > inEnd || postStart > postEnd) {27            return null;28        }29 30        // The last element in the current postorder segment is the root31        int rootVal = postorder[postEnd];32        TreeNode root = new TreeNode(rootVal);33 34        // Find the root's index in the inorder array (Linear Search)35        int rootIndex = -1;36        for (int i = inStart; i <= inEnd; i++) {37            if (inorder[i] == rootVal) {38                rootIndex = i;39                break;40            }41        }42 43        // Calculate the size of the left subtree44        int leftSubtreeSize = rootIndex - inStart;45 46        // Recursively build the left subtree47        root.left = buildHelper(inorder, inStart, rootIndex - 1, 48                                postorder, postStart, postStart + leftSubtreeSize - 1);49        50        // Recursively build the right subtree51        root.right = buildHelper(inorder, rootIndex + 1, inEnd, 52                                 postorder, postStart + leftSubtreeSize, postEnd - 1);53 54        return root;55    }56}