Construct Binary Tree from Inorder and Postorder Traversal | Leetcode

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

---

Solution: In each recursion, the last element in the postorder is always the root node. Find the root node in the inorder. Put everything on the left of the root node in the left sub-tree, and everything on the right of the root node in the right sub-tree.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private final Map<Integer, Integer> inOrderIndex = new HashMap<>();
    private int postOrderIndex;
    
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder.length == 0) return null;
        for (int i = 0; i < inorder.length; i++) {
            inOrderIndex.put(inorder[i], i);
        }
        postOrderIndex = postorder.length - 1;
        return buildTree(inorder, postorder, 0, inorder.length - 1);
    }
    
    private TreeNode buildTree(int[] inorder, int[] postorder, int i0, int i1) {
        if (i0 > i1) return null;
        TreeNode root = new TreeNode(postorder[postOrderIndex--]);
        int rootIndex = inOrderIndex.get(root.val);
        root.right = buildTree(inorder, postorder, rootIndex + 1, i1);
        root.left = buildTree(inorder, postorder, i0, rootIndex - 1);
        return root;
    }
}