106 Construct Binary Tree from Inorder and Postorder Traversal

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

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

For example, given

inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution)

First, create a root node with the end element of the post order and then find the index from the inorder.

Left part of the inorder based on the found index is left child and right part of the inorder based on the found index is right child.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode helper(int[] inorder, int is, int ie, int[] postorder, int pi, int pe, Map<Integer, Integer> map) {
        if (is > ie) return null;
        if (is == ie) return new TreeNode(inorder[is]);
        TreeNode node = new TreeNode(postorder[pe]);
        int idx = map.get(postorder[pe]);

        node.left = helper(inorder, is, idx-1, postorder, pi, pi+idx-is-1, map);
        node.right = helper(inorder, idx+1, ie, postorder, pi+idx-is, pe-1, map);
        return node;
    }
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        // create a hashmap for inorder
        Map<Integer, Integer> map = new HashMap<>();
        for (int i=0; i<inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return helper(inorder, 0, inorder.length-1, postorder, 0, postorder.length-1, map);
    }
}