# 根据前序、中序求后序📕

# 题目描述

输入某二叉树的前序遍历和中序遍历的结果,返回后序遍历结果

# 解题思路

这道题乍一看感觉和上面的《重建二叉树》差不多,只不过多出了一步返回后序遍历。说实话,刚开始看到题目我的想法竟然是先重建出二叉树,然后再调用后序遍历的函数(┬_┬)...

但是后来想了想还是应该利用每种遍历的特性来进行解题。

前面四项还是和《重建二叉树》的思路一样:

  1. 前序遍历的第一项一定是二叉树的根节点;
  2. 二叉树的根节点一定在中序遍历左子树和右子树的中间(包括没有左或右子树的情况): [左子树][根节点][右子树];
  3. 用前序遍历的第一项(也就是根节点)查找到它在中序遍历的第几项,左边的就是左子树,右边为右子树;
  4. 根据左右子树的长度,再次划分两个序列,进一步递归;
  5. 后序遍历的特性是根节点一定在最后:[左子树][右子树][根节点];
  6. 创建一个数组按照[左子树][右子树][根节点]的顺序依次推进去.

# coding

/*
* 根据前序遍历和中序遍历求后序遍历
* @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]
阅读全文