如何证明树的后序遍历序列等于对应二叉树的中序遍历序列

Question

树的遍历序列与对应二叉树的遍历序列之间具有如下对应关系:树的前序遍历序列等于对应二叉树的前序遍历序列,树的后序遍历序列等于对应二叉树的中序遍历序列

Answer 1

要证明一个树的后序遍历序列等于对应二叉树的中序遍历序列，需要先明确中序遍历和后序遍历的定义：

中序遍历：先访问左子树，再访问根节点，最后访问右子树。
后序遍历：先访问左子树，再访问右子树，最后访问根节点。
证明的思路是：根据后序遍历序列的最后一个元素（也就是根节点），可以确定中序遍历序列中根节点的位置，从而将中序遍历序列分成左右子树的序列。接下来，可以递归地对左右子树分别进行同样的操作，直到得到整个树的中序遍历序列。如果这个中序遍历序列和给定的中序遍历序列相同，那么就可以证明这个后序遍历序列对应的二叉树就是原来的树。

以下是具体的证明步骤：

首先，根据后序遍历的定义，最后一个元素是根节点。将这个根节点从后序遍历序列中删除，得到一个新的后序遍历序列。

根据中序遍历的定义，在中序遍历序列中找到根节点的位置。将中序遍历序列分成左右两个子序列，分别对应左子树和右子树。设左子树序列的长度为l，右子树序列的长度为r，则中序遍历序列可以表示为：

L1, L2, ..., Ll, 根节点, R1, R2, ..., Rr

其中，L1, L2, ..., Ll是左子树的中序遍历序列，R1, R2, ..., Rr是右子树的中序遍历序列。

然后，根据后序遍历的定义，左子树的后序遍历序列在整个后序遍历序列的前面，右子树的后序遍历序列在左子树的后面。因此，将新的后序遍历序列从左往右依次遍历，可以将后序遍历序列分成两个部分，分别对应左子树和右子树的后序遍历序列。设左子树的后序遍历序列为L，右子树的后序遍历序列为R，则后序遍历序列可以表示为：

L', R', 根节点

其中，L'和R'分别是左子树和右子树的后序遍历序列。

现在，对左子树和右子树分别进行同样的操作，即递归地进行