已知二叉树后序遍历序列是 dabec,中序遍历序列是debac,它的前序遍历序列是?
方法1:
首先可以确定c为根 d为最左子树
由中序debac 假设b为第2排的子树 那么后序的后两位应该是bc yu本题题目后序不符合
由中序debac 假设e为第2排的字数 那么后序的后两位应该是ec 符合本题题目后序
由后序dabec 可得两情况一种是 a为b的左子树 一种是a为b的右子树
但根据中序的左根右的特性 后序中的eba可知 a一定为b的右子树 否则根据左根右的特性 中序中a应该比b先输出
方法2 :