问题

Given inorder and postorder traversal of a tree, construct the binary tree.
** Notice
You may assume that duplicates do not exist in the tree.

Have you met this question in a real interview? Yes

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

分析

请参阅 Construct Binary Tree from Preorder and Inorder Traversal(前序遍历和中序遍历树构造二叉树)

代码

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) {
        // write your code here
        return buildTree(inorder,0,inorder.length-1,postorder,0,postorder.length-1);
    }
    private TreeNode buildTree(int[] preorder,int pleft,int pright, int[] inorder,int ileft,int iright){
        if(pleft>pright||ileft>iright){
            return null;
        }
        int i=inorder[iright];
        TreeNode node=new TreeNode(i);
        int index=pleft;
        while(preorder[index]!=i){
            index++;
        }
        int leftLength=index-pleft;
        node.left=buildTree(preorder,pleft,index-1,inorder,ileft,ileft+leftLength-1);
        node.right=buildTree(preorder,index+1,pright,inorder,ileft+leftLength,iright-1);
        return node;
    }
}