代码随想录算法训练营第14天｜二叉树Part02

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

LeetCode106. 从中序与后序遍历序列构造二叉树

var buildTree = function(inorder, postorder) {
    if (!inorder.length) return null;
    const rootVal = postorder.pop();
    // 从后序遍历的数组中获取中间节点的值， 即数组最后一个值
    let rootIndex = inorder.indexOf(rootVal);
    // 获取中间节点在中序遍历中的下标
    const root = new TreeNode(rootVal);
    // 创建中间节点
    root.left = buildTree(inorder.slice(0, rootIndex), postorder.slice(0, rootIndex));
    // 创建左节点
    root.right = buildTree(inorder.slice(rootIndex + 1), postorder.slice(rootIndex));
    // 创建右节点
    return root;
};

上面的代码每层递归定义了新的数组，浪费了一些时间空间。 可以将新数组在原数组中的首尾下标代替新数组实体作为参数在递归中传递：

var buildTree = function(inorder, postorder) {
    const build = (inLeft, inRight, postLeft, postRight) => {
        if (inLeft > inRight) return null;
        const rootVal = postorder[postRight];
        // 相当于 pop 出最后一个值
        const root = new TreeNode(rootVal);
        const rootIndex = inorder.indexOf(rootVal);
        // 根在中序中的位置
        const leftSize = rootIndex - inLeft;
        // 左子树节点数量
        root.left = build(inLeft, rootIndex - 1, postLeft, postLeft + leftSize - 1);
        // 递归构造左子树（对应 slice(0, rootIndex)）
        root.right = build(rootIndex + 1, inRight, postLeft + leftSize, postRight - 1);
        // 递归构造右子树（对应 slice(rootIndex + 1)）
        return root;
    };
    return build(0, inorder.length - 1, 0, postorder.length - 1);
};