如何证明树的后序遍历序列等于对应二叉树的中序遍历序列
树的遍历序列与对应二叉树的遍历序列之间具有如下对应关系:树的前序遍历序列等于对应二叉树的前序遍历序列,树的后序遍历序列等于对应二叉树的中序遍历序列
要证明一个树的后序遍历序列等于对应二叉树的中序遍历序列，需要先明确中序遍历和后序遍历的定义：
中序遍历：先访问左子树，再访问根节点，最后访问右子树。
后序遍历：先访问左子树，再访问右子树，最后访问根节点。
证明的思路是：根据后序遍历序列的最后一个元素（也就是根节点），可以确定中序遍历序列中根节点的位置，从而将中序遍历序列分成左右子树的序列。接下来，可以递归地对左右子树分别进行同样的操作，直到得到整个树的中序遍历序列。如果这个中序遍历序列和给定的中序遍历序列相同，那么就可以证明这个后序遍历序列对应的二叉树就是原来的树。
以下是具体的证明步骤：
首先，根据后序遍历的定义，最后一个元素是根节点。将这个根节点从后序遍历序列中删除，得到一个新的后序遍历序列。
根据中序遍历的定义，在中序遍历序列中找到根节点的位置。将中序遍历序列分成左右两个子序列，分别对应左子树和右子树。设左子树序列的长度为l，右子树序列的长度为r，则中序遍历序列可以表示为：
L1, L2, ..., Ll, 根节点, R1, R2, ..., Rr
其中，L1, L2, ..., Ll是左子树的中序遍历序列，R1, R2, ..., Rr是右子树的中序遍历序列。
然后，根据后序遍历的定义，左子树的后序遍历序列在整个后序遍历序列的前面，右子树的后序遍历序列在左子树的后面。因此，将新的后序遍历序列从左往右依次遍历，可以将后序遍历序列分成两个部分，分别对应左子树和右子树的后序遍历序列。设左子树的后序遍历序列为L，右子树的后序遍历序列为R，则后序遍历序列可以表示为：
L', R', 根节点
其中，L'和R'分别是左子树和右子树的后序遍历序列。
现在，对左子树和右子树分别进行同样的操作，即递归地进行
- 你可以参考下这个问题的回答, 看看是否对你有帮助, 链接: https://ask.csdn.net/questions/166530
- 我还给你找了一篇非常好的博客，你可以看看是否有帮助，链接：如何利用前序遍历序列和中序遍历序列非递归的创建二叉树
- 除此之外, 这篇博客: 已知一棵树二叉树的后根遍历和中根遍历的序列写出它的先根序列或者已知一棵树二叉树的先根遍历和中根遍历的序列写出它的后根序列中的 解题思路： 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
我们先找到根
后根：左 右 根 中跟：左 根 右
ACDB GIHF E ABCD E FGHI
我们先从后根去找，这个根一定是在这个遍历的后面，我们就可以确定E是根
然后我们在中根遍历中找到E的位置，所以E的左边就是左指数节点，右边是右指数节点
现在最上面的数E确定了，那谁是E左指数上的根呢，谁在后面谁是根：是B
然后再看中根遍历，谁在B的左边谁是左指数：是A；于是:
现在在左指数上只有C和D没有画出来，
看中根遍历得到：C和D在B的右边，看后根遍历知道D在后面，所以D是根，
在中根遍历中，C在D的左边，所以C是D的左指数；
于是：以E为根节点的左指数画完
接下来看看以E为根节点的右指数，先在后根遍历中找根节点，谁在后面谁是根节点：是F
再到中根遍历中找到F位置，F左边画完了，所以没有左指数，再看右边：GHI
回到后根遍历看GHI，得知H是根节点，所以：
现在只剩G、I 没有画了，所以回到中根遍历中看到G在H左，I 在H右，所以：
如果想知道画的对不对，带进题干，看看他的后根遍历和中根遍历对不对就行了
- 您还可以看一下 张传波老师的软件设计是怎样炼成的？课程中的 架构设计的第二层拆解小节, 巩固相关知识点