重建二叉树

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路：

在二叉树的前序遍历中，第一个的值即二叉树的根节点，由此可以在中序遍历序列中找到根节点，根节点左边的是二叉树的左子树，右边的是二叉树的右子树。因此可以使用递归不断重建二叉树，递归的结束条件即前序遍历的左index大于右index的时候结束递归。具体的可以看下图：

代码：

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    if(pre == null || in == null || pre.length != in.length
        || pre.length == 0 || in.length ==0) {
        return null;
    }
    
    return helper(pre, 0, pre.length-1, in, 0, in.length-1);
}

private TreeNode helper(int[] pre, int lp, int rp, int[] in, int li, int ri) {
    if (lp > rp) {
        return null;
    }
    
    TreeNode root = new TreeNode(pre[lp]);
    int i;
    for (i = li; i <= ri; ++i) {
        if (root.val == in[i]) {
            break;
        }
    }
    
    root.left = helper(pre, lp+1, lp + (i-li), in, li, i-1);
    root.right = helper(pre, lp + (i-li) + 1, rp, in, i+1, ri);
    
    return root;
}

--------EOF--------