根据前序、中序求后序|博客系列

/*
* 根据前序遍历和中序遍历求后序遍历
* @param {Array} preorder
* @param {Array} inorder
* @return {Array} 后序结果
*/
function getPost (preOrder, inOrder) {
    let list = [] // 定义一个栈用于存储后序结果
    let getPostFn = function (preOrder, inOrder) {
        if (!preOrder.length || !inOrder.length) { // 若是先序遍历或中序遍历为空则返回null
            return null
        }
        let root = preOrder[0] // 根节点为先序遍历的第一项
        let i = inOrder.indexOf(root) // 查找到根节点在中序遍历中的位置

        let left = getPostFn(preOrder.slice(1, i + 1), inOrder.slice(0, i))
        let right = getPostFn(preOrder.slice(i + 1), inOrder.slice(i + 1))

        if (left) list.push(...left) // 先推进所有的左子树列表
        if (right) list.push(...right) // 在推进所有的右子树列表
        list.push(root) // 最后推入根节点
    }
    getPostFn(preOrder, inOrder)
    return list
}
const preArray = [1, 2, 4, 7, 3, 5, 6, 8];
const midArray = [4, 7, 2, 1, 5, 3, 8, 6];
const postArray = getPost(preArray, midArray)
// [7,4,2,5,8,6,3,1]