题目描述（中等难度）

根据二叉树的中序遍历和后序遍历还原二叉树。

思路分析

可以先看一下 105 题，直接在 105 题的基础上改了，大家也可以先根据 105 题改一改。

105 题给的是先序遍历和中序遍历，这里把先序遍历换成了后序遍历。

区别在于先序遍历的顺序是根节点 -> 左子树 -> 右子树。

后序遍历的顺序是左子树 -> 右子树 -> 根节点。

对于之前的解法一，传数组的两个边界，影响不大，只要重新计算边界就可以了。

但是对于另外两种解法，利用 stop 和栈的算法，之前都是通过遍历前序遍历的数组实现的。所以构造过程是根节点，左子树，右子树。

但这里如果是后序遍历，我们先找根节点，所以相当于从右往左遍历，这样的顺序的话就成了，根节点 -> 右子树 -> 左子树，所以我们会先生成右子树，再生成左子树。

常规解法，利用递归，传递左子树和右子树的数组范围即可。

这里的话，之前说了，递归的话得先构造右子树再构造左子树，此外各种指针，也应该从末尾向零走。

和都从右往左进行遍历，所以开始产生的每次都是右子树的根节点。之前代码里的要相应的改成。

之前解法是构造左子树、左子树、左子树，出现相等，构造一颗右子树。这里相应的要改成构造右子树、右子树、右子树，出现相等，构造一颗左子树。和解法二一样，两个指针的话也是从末尾到头部进行。

理解了的话，这道题很快就出来了，完全是 105 题的逆向思考。

添加好友一起进步~

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击这里查看详情