思路
-
1 确定根,确定左子树，确定右子树。
根是pre_order的第一个节点
在in_order中找到根的位置i -
2 在左子树中递归。
pre_order 切片 [1:i + 1]
in_order 切片 [:i] -
3 在右子树中递归。
pre_order 切片 [i + 1:]
in_order 切片 [i + 1:] -
4 打印当前根。
do(pre_order[0])
或者do(in_order[i]) -
关键问题在于为什么打印当前根就是后序遍历了？
首先我们看，最外层的根节点是最后输出的。
可以思考出来，每一层的父节点都一定在它的孩子节点之后输出。
同层的两棵树，从它们共同根节点的角度来看，是左子树先输出，然后才输出右子树。
所以从深度和广度两个层面看，是后续遍历的结果。
复杂度分析
- 空间复杂度
最坏情况：递归栈复杂度o(n) ：所有子树全部为右子树或左子树
最好/一般情况：递归栈复杂度o(log2n) ：完全二叉树/除了所有子树全部为右子树或左子树的二叉树
- 时间复杂度
每一次的搜索根节点的复杂度在o(n)
最坏情况：递归栈复杂度o(n) ：所有子树全部为右子树或左子树
最好/一般情况：递归栈复杂度o(log2n) ：完全二叉树/除了所有子树全部为右子树或左子树的二叉树
总结起来
最坏情况：递归栈复杂度o(n2)
最好/一般情况：递归栈复杂度o(nlog2n)
优化方案
输入数据前的预处理，在构造树的时候尽量向完全二叉树靠拢。
参考快速排序的随机化序列方法，目前还没思路
相似问题
知道前序遍历和中序遍历可以唯一确定一棵二叉树
知道中序遍历和后序遍历可以唯一确定一棵二叉树
知道层次遍历和中序遍历可以唯一确定一棵二叉树
知道前序遍历和后序遍历不能唯一确定一棵二叉树
