JavaScript实现重建二叉树

重建二叉树的实现思路：根据二叉树中先序遍历和中序遍历特点求解。

1. 首先确定二叉树根节点的值rootValue，先序序列中的第一个值即为根节点的值，接着在中序序列中找到rootValue的位置，位于rootValue左边的序列为左子树，位于rootValue右边的序列为右子树。这样我们就确定了根节点以及它的两个子树。
2. 确定根节点的左孩子，先序序列中位于根节点值rootValue后面第一个值就是根节点的左孩子。递归第一步，就可以确定所有节点的左孩子了。
3. 确定根节点的右孩子，先序序列中位于值rootValue的位置 + 左子树的长度的位置上的值就是根节点的右孩子。递归第一步，就可以确定所有节点的右孩子。
4. 迭代过程中，要注意书写终止条件，否则就会一直执行导致栈溢出。如何设置终止条件呢？我们注意到二叉树的叶子节点是没有孩子的，所以只要节点的子树长度 < 1时，就返回这个节点，结束迭代。

JavaScript代码实现如下：

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function reConstructBinaryTree(pre, vin)
{
    if(pre.length !== vin.length) return false;
    return construct(pre, 0, vin, 0, vin.length);
}
function construct(preOrder, preOrderStart, inOrder, inOrderStart, length) {
    // 先序序列中第一个值为根节点的值
    var rootValue = preOrder[preOrderStart],
        root = new TreeNode(rootValue);

    if(length <= 1) {
        return root;
    }

    // 在中序序列中找到根节点的值，确定左子树，右子树
    var rootInorder = inOrder.indexOf(rootValue),
        leftLength =  rootInorder - inOrderStart,
        rightLength = length - 1 - leftLength;

    if(leftLength > 0) {
        root.left = construct(preOrder, preOrderStart + 1, inOrder, inOrderStart, leftLength);
    }
    if( rightLength > 0) {
        root.right = construct(preOrder, preOrderStart + 1 + leftLength, inOrder, rootInorder + 1, rightLength);
    }
    return root;
}