SOURCE

// 思路
// 注意 一个前提 前中后序 数组长度 相同
// 由前序(中左右)或后序(左右中)遍历获取的节点序列 中节点都是在其末端 因此可以确定中节点是哪个
// 再结合中序(左中右)遍历得到的序列 以中节点位置 在中序序列中分割出左右子树
// 再以中序的左右子树数组长度 从 后序数组 头部开始 分割 出左右子树数组 传递给下一层递归
// 从而构建出二叉树

function fn(中序数组, 后序数组) {
    // 中序和后序长度相同 有一个为空就返回null
    if (!中序数组.length) return null
    // 迭代时先从后序数组末尾弹出中节点
    let 中节点 = 后序数组.pop()
    // 创建中节点
    let 节点 = {
        value: 中节点,
    }
    // 根据中节点在 中序数组中定位 分割成左右子树数组
    let 中节点位置 = 中序数组.indexOf(中节点)
    // 左子树 从 中序数组 的 起始位置 到 中节点位置 进行分割
    // 后序数组 从 起始位置 到 中节点位置(即中序左子树长度) 进行分割
    // 注意 slice是左闭右开
    节点.left = fn(中序数组.slice(0, 中节点位置), 后序数组.slice(0, 中节点位置))
    // 右子树 从 中序数组 的 中节点位置+1 到 数组末尾
    // 后序数组 从 中节点位置 到 数组末尾
    // 注意 因为后序相比于中序 其中节点从左右子树中间移到了末尾 也就是说右子树往前移了一位
    // 因此 中节点位置 就是右子树在后序中的起始索引
    // 注意 后序数组 在前面已经pop 因此不用考虑中节点
    节点.right = fn(中序数组.slice(中节点位置 + 1), 后序数组.slice(中节点位置))
    return 节点
}

// 验证
let 中序数组 = [9, 3, 15, 20, 7]
let 后序数组 = [9, 15, 7, 20, 3]
console.log('模拟的二叉树', fn(中序数组, 后序数组))