12 construct-binary-tree-from-ino

题目描述

给出一棵树的中序遍历和后序遍历，请构造这颗二叉树
注意：
保证给出的树中不存在重复的节点

思路：左子树-中序数组 is = is, ie = ri - 1
左子树-后序数组 ps = ps, pe = ps + ri - is - 1 (pe计算过程解释，后续数组的起始位置加上左子树长度-1 就是后后序数组结束位置了，左子树的长度 = 根节点索引-左子树)
右子树-中序数组 is = ri + 1, ie = ie
右子树-后序数组 ps = ps + ri - is, pe - 1

public TreeNode buildTree (int[] inorder, int[] postorder) {
        if(inorder==null||postorder==null||inorder.length!=postorder.length)
        {
            return null;
        }
        return solve(inorder,postorder,0,inorder.length-1,0,postorder.length-1);
    }
    public TreeNode solve(int[] inorder, int[] postorder,int ib,int ie,int pb,int pe) {
        if(ib>ie||pb>pe) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[pe]);
        for(int i=ib;i<=ie;i++) {
            if(inorder[i] == postorder[pe]) {
                root.left = solve(inorder,postorder,ib,i-1,pb,pb+i-ib-1);
                root.right = solve(inorder,postorder,i+1,ie,pb+i-ib,pe-1);
                break;
            } 
        }
        return root;
    }