文章目录

引言:我想到一个绝妙的方法,在已知前序遍历和中序遍历或已知中序遍历和后序遍历时推得二叉树。


灵光来自:https://blog.csdn.net/mercy_ps/article/details/82530278

已知前序或后序,其实是得知各个结点的层序关系。先序遍历中,先得到的结点的高度必定大于后得到的结点的高度,或分处不同分支;后序遍历中,后得到的结点的高度必定大于先得到的结点的高度,或分处不同分支。

如中序遍历:DCBGEAHFIJK

后序遍历:DCEGBFHKJIA

则先找到根A,由于中序遍历先打印左节点,再打印根节点。在中序遍历中用A将结点分为DCBGE|HFIJK。

再找到I,将右树分为HF|JK

再找到J,因此K在右边,且J是K父亲。

再找到K,已经分好了,略过。

再找到H,所以F在右边,H是F的父亲。

再找到F,已经分好了,略过。

再找到B,将DCBGE分为DC|GE

再找到G,G是E的父亲且E在右边。

再找到E,略过。

再找到C,C是父亲且在D右边。

好,再填上作分割的结点,上图:

已知前序遍历和中序遍历时同理。

好吧其实上述不是我的绝妙的方法,但我发现上述法子大家都会,而且貌似比我那个法子要好。

那么拙计就不放了。

文章目录