根据先序遍历序列中序遍历序列重建二叉树

Java题解

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        int h1 = pre.length - 1;
        int h2 = in.length - 1;
        TreeNode treeNode = buildTree(pre, in, 0, h1, 0, h2);
        return treeNode;
    }

    /**
     *
     * @param pre 先序序列
     * @param in 中序序列
     * @param l1 先序起点下标 0
     * @param h1 先序终点下标 pre.length - 1
     * @param l2 中序起点下标 0
     * @param h2 中序终点下标 in.length - 1
     * @return
     */
    public TreeNode buildTree(int[] pre, int[] in, int l1, int h1, int l2, int h2){
        // 新建节点
        TreeNode node = new TreeNode(pre[l1]);
        // 划分序列
        int i=l2;
        for( ; in[i]!=node.val; i++);
        // 左子树节点个数
        int llen = i-l2;
        // 右子树节点个数
        int rlen = h2-i;
        // 建左子树
        if(llen>0){
            node.left = buildTree(pre, in, l1+1, l1+llen, l2, l2+llen-1);
        }else {
            node.left = null;
        }
        // 建右子树
        if(rlen>0){
            node.right = buildTree(pre, in, h1-rlen+1, h1, h2-rlen+1, h2);
        }else {
            node.right = null;
        }
        return node;
    }
}