前、中、后序,知道其中哪两个就可以还原二叉树?请予以证明,或者随便举个反例说明

Question

前、中、后序,知道其中哪两个就可以还原二叉树?
请予以证明,或者随便举个反例说明

Answer 1

1. 知道一棵二叉树（二叉树的子树也是二叉树）的前序和后序序列,就可以知道这棵二叉树的根.因为前序的第一个结点是当前这棵二叉树的根,后序序列的最后一个结点是根
2. 知道一棵二叉树的根,同时知道其中序序列,就可以知道根的左子树序列和右子树序列.因为中序序列中的根前的结点属于左子树,根后的结点属于右子树（这个由中序序列的遍历性质可知）
3. 所以只要知道前序和中序,或者中序和后序即可还原二叉树
4. 而只知道前序和后序无法保证还原二叉树,例如二叉树
A 与 A
B B
C C
的前序序列都是ABC,而后序序列都是CBA