剑指Offer-Javascript版-重建二叉树

给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

    3
   / \
  9  20
    /  \
   15   7

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var buildTree = function(preorder, inorder) {
    if(!preorder.length || !inorder.length) {
        return null
    }

    const rootVal = preorder[0]
    const node = new TreeNode(rootVal)

    // i有两个含义，一个是根节点在中序遍历结果中的下标， 另一个是当前左子树的节点个数
    let i = 0;
    for(; i < inorder.length; ++i) {
        if(inorder[i] === rootVal) {
            break;
        }
    }

    // i主要是求出根节点在中序遍历序列中的位置。那么i位置前面的都是左子树的值，后边的都是右子树的值。
    // 中序遍历和前序遍历的左子树和右子树节点的个数都分别相等
    node.left = buildTree(preorder.slice(1, i+1), inorder.slice(0, i))
    node.right = buildTree(preorder.slice(i+1), inorder.slice(i + 1))

    return node
};