题目:通过二叉树的中序和后序遍历序列构造二叉树
同样,使用分治法来实现是完全可以的,可是在leetcode中运行这种方法的代码,总是会报错:
,所以这里还是用栈来实现二叉树的构建。
与用先序和后序遍历构造二叉树的方法类似,但还是要做一些改变:
如果从后往前处理中序和后序的序列,则处理就为如下所示的情况:
reverse_post: 根—右子树—左子树
reverse_in: 右子树—根—左子树
这样处理方式和先序—中序就差不多了,只是将添加左孩子的情况,改为添加右孩子,反之依然。
实现代码如下所示: