Question

二叉树遍历问题

请问下图所示的二叉树的
前序遍历是：
中序遍历是：
后序遍历是：
A
∕＼
B C
∕ ∕＼
D E F
＼ ∕＼
G H I
前，中，后序遍历序列都是什么？
还有，告诉其中两个序列就能得出第三个序列？怎么得到的？
已知二叉树后序遍历序列是bfegcda，中序遍历序列是badefcg，它的前序遍历序列是？（给出具体思路）给的好加分

Answer 1

abdcefg 按照二叉树几种遍历的特点，分析:首先要确认根结点；由后序遍历结果可以得到根节点是a；再由中序遍历可以得到左子树只有结点b，defcg都在右子树；然后由后序遍历判断出右子树的根为d。。。。。

Answer 2

对于二叉链式存储的二叉树，各种遍历方式都至少得用到栈（包括递归）或者队列结构吧……
于是乎O(1)的空间有可能吗？求原题详细描述并坐等高手……

Answer 3

前：A,B,D,G,C,E,F,H,I
中：D,G,B,A,E,C,H,I,F
后：G,D,B,E,H,I,F,C,A