題目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.

1,

在盜用一圖

IMG_20161227_173459.jpg

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || postorder.length == 0){
            return null;
        }
        
       return createTree(postorder, postorder.length-1, inorder, 0, inorder.length-1);
    }
    
    
    private TreeNode createTree(int[] postorder ,int postIdx, int[] inorder, int inStartIdx, int inEndIdx){
        if(postIdx < 0){
            return null;
        }
        
        if(inStartIdx > inEndIdx){
            return null;
        }
        int rootVal = postorder[postIdx];
        TreeNode root = new TreeNode(rootVal);
        int rootIdxIn;
        for(rootIdxIn=inStartIdx; rootIdxIn<=inEndIdx; rootIdxIn++){
            if(rootVal == inorder[rootIdxIn]){
                break;
            }
        }
        
        root.left = createTree(postorder,postIdx-(inEndIdx-rootIdxIn)-1,inorder,inStartIdx,rootIdxIn-1);
        root.right = createTree(postorder,postIdx-1,inorder,rootIdxIn+1,inEndIdx);
        return root;
    }
}