JavaScript题解剑指offer : 07. 重建二叉树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function(preorder, inorder) {
    return diGui(preorder,inorder);
};
function diGui(preorder,inorder) {
    if(!preorder.length) { // 先序遍历为空null
        return null;
    }
    let value = preorder[0],i; // 利用根节点在钱序遍历节点序列中的第一位特性
    let root = new TreeNode(value); // 创建根节点
    if(preorder.length === 1) return root; // 没有子节点的根节点
    for(i = 0; i < inorder.length; i++) { // 先序遍历找到的根节点在中序遍历循环遍历查找位置，用于递归分割子树。
        if(value === inorder[i]) break;
    }
    let leftInorder = inorder.slice(0, i), rightInorder = inorder.slice(i + 1); // 将先序遍历分割
    let leftPreorder = preorder.slice(1, leftInorder.length + 1), rightPreorder = preorder.slice(leftInorder.length + 1); // 将中序遍历分割
    // 进行递归
    root.left = diGui(leftPreorder,leftInorder); 
    root.right = diGui(rightPreorder, rightInorder);
    return root;
}