Construct Binary Tree from Inorder and Postorder Traversal

Source

• lintcode: Construct Binary Tree from Inorder and Postorder Traversal

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

Example
Given inorder [1,2,3] and postorder [1,3,2], return a tree:

  2
 / \
1   3
Note
You may assume that duplicates do not exist in the tree.

Java

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */


public class Solution {
    /**
     *@param inorder : A list of integers that inorder traversal of a tree
     *@param postorder : A list of integers that postorder traversal of a tree
     *@return : Root of a tree
     */
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int len = inorder.length;    
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  
        for (int i=0; i < len; ++i) {    
            map.put(inorder[i], i);    
        }    
        return buildSubTree(postorder, len-1, map, 0, len-1);    
    }  


    private TreeNode buildSubTree(int[] postorder, int cur, HashMap<Integer, Integer> inorder, int start, int end) {    
        if (start > end)  return null;  

        TreeNode root = new TreeNode(postorder[cur]);    
        int mid = inorder.get(postorder[cur]);    
        root.left = buildSubTree(postorder, cur-(end-mid)-1, inorder, start, mid-1);    
        root.right = buildSubTree(postorder, cur-1, inorder, mid+1, end);    
        return root;    
    }  
}