JunyiCode
4/2/2020 - 3:43 AM

106. Construct Binary Tree from Inorder and Postorder Traversal

O(n) && O(n) for Solution 2

/*
solution 2 is faster because of HashMap
The basic idea is to take the last element in postorder array as the root, find the position of the root in the inorder array
*/

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        return helper(postorder.length - 1, 0, inorder.length - 1, inorder, postorder);
    }
    
    private TreeNode helper(int postEnd, int inStart, int inEnd, int[] inorder, int[] postorder) {
        if(postEnd < 0 || inStart > inEnd)  
            return null;
        
        TreeNode root = new TreeNode(postorder[postEnd]); 
        int inRoot = 0;
        
        for(int i = inStart; i <= inEnd; i++) {
            if(root.val == inorder[i])
                inRoot = i;
        }
        
        int numsRight = inEnd - inRoot;
        
        root.left =  helper(postEnd - numsRight - 1, inStart, inRoot - 1, inorder, postorder);
        root.right = helper(postEnd - 1, inRoot + 1, inEnd, inorder, postorder);
            
        return root;
    }
}
/*
比第一种多了map
*/

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder == null || postorder == null || inorder.length != postorder.length)
		return null;
	HashMap<Integer, Integer> map = new HashMap<Integer,Integer>();
	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);
    }
    
    public TreeNode helper(int[] inorder, int inStart, int inEnd, int[] postorder, int postStart, int postEnd, HashMap<Integer,Integer> map){
        if(inStart > inEnd || postStart > postEnd) 
            return null;
        int inRoot = map.get(postorder[postEnd]);
        TreeNode root = new TreeNode(postorder[postEnd]);
        int len = inRoot - inStart;
        root.left = helper(inorder, inStart, inRoot - 1, postorder, postStart, postStart + len - 1, map);
        root.right = helper(inorder, inStart + len + 1, inEnd, postorder, postStart + len, postEnd - 1, map);
        return root;
    }
}