【剑指 Offer】07. 重建二叉树

[sayid760]

原因

[sayid760]

function TreeNode(val) {
    this.val = val;
    this.left = this.right = null;
}

/*
    1）前序的第一个是树的顶点，用这个顶点在中序找出对应的左边和右边
    2）找到中序的对应左边右边后，递归构建左边树和右边树
    3）返回整棵树
*/
var buildTree = function (preorder, inorder) {
    if(!preorder.length || !inorder.length) return null
    const rootVal = preorder[0];
    const node = new TreeNode(rootVal);
    let i = 0; // i有两个含义，一个是根节点在中序遍历结果中的下标，另一个是当前左子树的节点个数
    for (; i < inorder.length; ++i) {
        if (inorder[i] === rootVal) { // 说明找到中序了
            break;
        }
    }
    // slice(从什么开始，到什么结束且不包括结束位置)   前序的1位置（下标0已经是根节点） ， 中序的左侧位置
    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;
};

let preorder = [3, 9, 20, 15, 7]
let inorder = [9, 3, 15, 20, 7]
console.log(buildTree(preorder, inorder))