二叉树已知中序后序求先序遍历

二叉树是一种常见的数据结构，其可以用于解决许多问题。在处理二叉树问题时，经常需要对其进行遍历。二叉树的遍历方式有三种：先序遍历、中序遍历和后序遍历。先序遍历顺序是根节点、左子树、右子树；中序遍历顺序是左子树、根节点、右子树；后序遍历顺序是左子树、右子树、根节点。若中序遍历和后序遍历序列已知，如何求出先序遍历序列呢？这是一个有趣的问题，本文将从多个角度分析。

一、二叉树基础知识

在讨论解决问题之前，首先需要了解二叉树的基础知识。二叉树是一种特殊的树形结构，其由根节点、左子树和右子树组成。每个节点最多有两个子节点，左子节点在右子节点的左边。

二叉树的性质有：

1.非空二叉树第i层上的结点数最多为2^(i-1)，i>=1;

2.深度为k的二叉树至多有2^k -1个节点；

3.对于任意一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。

二、从中序和后序遍历序列推断先序遍历

中序遍历和后序遍历的特性在于：中序遍历序列中最先访问的是根节点左侧的子节点，后序遍历序列中最后访问的是根节点左侧的子节点，因此可以通过中序和后序遍历的序列，确定左右子树的范围和根节点来确定先序遍历序列。

比如，有如下一颗二叉树：


其中中序遍历序列为：2 1 4 6 5 3；后序遍历序列为：2 6 4 5 3 1。可以利用这些知识推导出其先序遍历序列：

- 从后序遍历序列中找到根节点，即1；

- 在中序遍历序列中找到1，划分出左、右子树的中序遍历序列为：左子树为2；右子树为4 6 5 3；

- 利用划分出的左、右子树中序遍历序列，在后序遍历序列中找到对应位置的子序列，即：左子树为2；右子树为6 4 5 3；

- 通过上述步骤，可以得到左、右子树的后序遍历序列和中序遍历序列，可以递归求出左、右子树的先序遍历序列，从而得到整颗树的先序遍历序列。

因此，对于任意一颗二叉树，已知中序遍历序列和后序遍历序列即可求出其先序遍历序列。

三、代码实现

通过上述分析，可以写出如下代码实现：

```python

def build_preorder(inorder, postorder):

if not inorder or not postorder:

return []

root = postorder[-1]

index = inorder.index(root)

left_inorder = inorder[:index]

right_inorder = inorder[index+1:]

left_postorder = postorder[:index]

right_postorder = postorder[index:-1]

return [root] + build_preorder(left_inorder, left_postorder) + build_preorder(right_inorder, right_postorder)

```

四、总结

在本文中，我们介绍了二叉树的基础知识，详细解释了如何通过中序和后序遍历序列推断出先序遍历序列，并提供了相应的代码实现。在实际应用中，先序、中序、后序遍历序列都有重要的作用，掌握这些知识是解决二叉树问题的基础和关键。