知道前序遍历和中序遍历可以唯一确定一棵二叉树
知道中序遍历和后序遍历可以唯一确定一棵二叉树
知道层次遍历和中序遍历可以唯一确定一棵二叉树
知道前序遍历和后序遍历不能唯一确定一棵二叉树
上面这些应该大部分 数据结构 的教科书都有讲的，但对于只知道前序遍历和后序遍历的情况书上和网上提及得都比较少。
知道前序和后序不能唯一确定一棵二叉树是肯定的，比如前序遍历是”AB“，后序遍历是”BA“，可以很容易知道A是树的根，然后根据B是A的左孩子和B是A的右孩子两种情况就可以构造出两种二叉树。但这只是有序树的情况，如果放在无序树里呢？根据著名的（著名吗？- -）数据结构教材”天勤“里面的定义：
- 有序树：树中结点的子树从左到右是由次序的，不能交换。
- 无序树：树中结点的子树没有顺序，可以任意交换。
另外根据网上一些讨论说道前序和后序只反映了结点间的父子关系，没有反映左右关系，但我自己画了一下， 好像有某种方法可以把某些左右关系反映出来的- -
首先假设一种前序遍历的记法是”nLR“，一种后序遍历的记法是”LRn“，n代表当前遍历到的子树的根，L代表n的左子树，R则是右子树。在遍历时首先是：
nLR , LRn
逗号左表示前序遍历，右则是后序遍历，然后如果把L和R展开一下：
nn_{l}L_{l}R_{l}n_{r}L_{r}R_{r} , L_{l}R_{l}n_{l}L_{r}R_{r}n_{r}n
好像已经可以看出一些东西了，
- 在前序遍历的最左侧的n是当前子树的根，在后序遍历中最右侧的是当前子树的根，
- 在前序遍历的左侧第二的n_{l}是n的左子树的根，在后序遍历的倒数第二的n_{r}是n的右子树的根，
- 知道n_{l}和n_{r}后，只需要在前序序列中的n_{r}或在后序序列中的n_{l}右侧画一条竖线，就可以把n的左右子树区分开了，
- 由于这是一个递归的方法，所以从根开始就可以把整棵树所有结点的左右子树分开了。
但这种方法好像只能用于同时有左右子树的结点，理由是推导时假设了前序是”nLR“后序是”LRn“的模式，而且上面也提及过当一个结点只有一棵子树的话是不能区分左右的。但是反正无序树也不管左右
然后最后给一个e.g.
首先是这样一棵树：
解出来是这样的：
https://drive.google.com/file/d/10Lz4XA1JBE9ceA3ioKiDRqjEfsYWnoOn/view?usp=sharing
（图片传不了，先咕一会补）
PS：以上都是自己做题时xjb写出来的，来个兄弟帮忙纠下错呗（不然都不敢用了:）