二叉树中等 LeetCode106. 从中序与后序遍历序列构造二叉树

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

• 与105题思路是一样的，找到根节点，将中序遍历的数组划分成左右两半，计算这左右两半的长度，将后序遍历的数组划分成两半，最后递归求左右孩子。
• 不要真的切分数组，使用左右边界下标标记范围。

class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length == 0){
            return null;
        }
        return build(inorder,postorder,0,inorder.length-1,0,inorder.length-1);
    }

    public TreeNode build(int[] inorder, int[] postorder, int istart, int iend, int pstart, int pend){
        if(istart > iend){
            return null;
        }
        if(istart == iend){
            return new TreeNode(inorder[istart]);
        }
        int i = istart; 
        while(i <= iend && inorder[i] != postorder[pend]){
            i++;
        }
        TreeNode newnode = new TreeNode(postorder[pend]);
        int leftlen = i - istart;
        newnode.left = build(inorder,postorder,istart,i-1,pstart,pstart+leftlen-1);
        newnode.right = build(inorder,postorder,i+1,iend,pstart+leftlen,pend-1);
        return newnode;
    }
}