天天看点

通过二叉树的中序和后序遍历序列构造二叉树(非递归)

题目:通过二叉树的中序和后序遍历序列构造二叉树

同样,使用分治法来实现是完全可以的,可是在leetcode中运行这种方法的代码,总是会报错:

 ,所以这里还是用栈来实现二叉树的构建。

与用先序和后序遍历构造二叉树的方法类似,但还是要做一些改变:

通过二叉树的中序和后序遍历序列构造二叉树(非递归)
通过二叉树的中序和后序遍历序列构造二叉树(非递归)
通过二叉树的中序和后序遍历序列构造二叉树(非递归)

如果从后往前处理中序和后序的序列,则处理就为如下所示的情况:

reverse_post: 根—右子树—左子树

reverse_in: 右子树—根—左子树

通过二叉树的中序和后序遍历序列构造二叉树(非递归)

这样处理方式和先序—中序就差不多了,只是将添加左孩子的情况,改为添加右孩子,反之依然。

实现代码如下所示: