重建二叉树【转载】
二叉树遍历方式：
- 前序遍历【根左右】；
- 中序遍历【左根右】；
- 后续遍历【左右根】；
重建二叉树：
- 前序+中序；2. 中序+后续；3.前序+后续；
注意： 第3种情况无法重建惟一二叉树的，因为无法知道结点是属于左子树还是右子树；
此文以中序与后续遍历结果为例——重建二叉树。
如图，例子来说明。知道中序HDMIBJNEAFKCG和后序遍历HMIDNJEBKFGCA，画二叉树和写出前序遍历。
从后序遍历知道，最后一个必然是根节点，因此A是根。再结合中序遍历可知HDMIBJNE是A的左子树部分，FKCG是右子树部分。
取A的右子树部分来看先，右子树部分的中序遍历：FKCE，后序遍历：KFGC。接着从后序遍历中看A的右子树部分KFGC，所以C是根。又从中序遍历知，FK是C的左子树部分，G是C右子树。如图所示
使用同样的方法，C的左子树部分，中序：FK，后序：KF。可以得出F是根，那么K只能是F的右子树了。此时如图所示，A的右子树部分都出来了。
再看，A的左子树部分HDMIBJE，中序：HDMIBJNE，后序：HMIDNJEB。后序遍历可知，B是根结点，那么再结合中序遍历可知道HDMI是B的左子树部分，JNE是B的右子树部分。
紧接着就是看B的左子树部分HDMI，中序：HDMI，后序：HMID，可知D是根，H是D的左子树，MI是D的右子树部分，如图所示。
看到D的右子树部分，中序后序都是MI，根据后序中序的特性可知道，根只能是I，M是I的左子树。
再接着看看B的右子树部分JNE，中序：JNE，后序：NJE，后序看出E是根，中序看出E无右子树，只有JN是E的左子树部分。
最后看JN的中序：JN，后序：NJ，根据后序特性看出，J是根，中序看出N是J的右子树。那么整体的二叉树就出来了，如图所示。
牛刀小试。
已知中序遍历：ACQVLCOJYPRKSXG后序遍历：AVQCOCJLRSKPGXY画出二叉树，并写出前序遍历。
二叉树如图所示，前序遍历是YLCAQVJCOXPKRSG
以上内容来自：