根据前序遍历和中序遍历得到二叉树后续遍历（一看就懂）

Dear 丶 2022-12-16 15:29 97阅读 0赞

文章转载自：[https://www.cnblogs.com/jiaxin359/p/9512348.html][https_www.cnblogs.com_jiaxin359_p_9512348.html]

# 根据树前序遍历和中序遍历构建二叉树 #

问题：已知一个二叉树前序遍历为：ABDEGCFH，中序遍历为：DBGEACHF，则该二叉树的后序遍历为？

思路是这样的：1：根据前序遍历来确定每次根节点的位置，因为前序遍历先访问的是根节点，所以前序遍历第一个位置就是根节点。 2：根据根节点和中序遍历将树划分为左右两棵树。3：根据第一步和第二步递归的处理左右两棵树。

**第一步**：根据前序遍历 **A B D E G C F H** 确定头结点是A，根据中序遍历 **D B G E A C H F** 将树划分为左子树 **D B G E** 和右子树 **C H F**。  
**第二步**：划分为左右两棵子树：对于左子树，前序遍历是 **B D E G**，后续遍历是 **D B G E**。对于右子树，前序遍历是 **C F H**，后续遍历是 **C H F**。  
**第三步**：对左子树和右子树分别运用第一步和第二步进行分析。  
**递归结束的条件**：当中序遍历的节点只剩下一个节点的时候，那么这个节点就是叶子节点。

整个流程参考如下截图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70][]

# 根据树后序遍历和中序遍历构建二叉树 #

道理是一样的，根据后序遍历来确定根节点的位置，由于后序遍历最后访问根节点， 所以此时最后一个节点就是根节点。根据中序遍历来划分左右子树，然后迭代求解。

# 根据树前序遍历和后序遍历不能构建唯一的二叉树 #

前序和后序在本质上都是将父节点与子结点进行分离，但并没有指明左子树和右子树的能力，因此得到这两个序列只能明确父子关系，而不能确定一个二叉树。  
比如前序遍历为ABC，后续遍历为CBA，可以构造出下面两棵树，可以发现这并不唯一：

如下图所示：

![20201021091318654.png][]

[https_www.cnblogs.com_jiaxin359_p_9512348.html]: https://www.cnblogs.com/jiaxin359/p/9512348.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70]: /images/20221123/a3f3abd902c84d0f9e3fcb39f1d7c6cc.png
[20201021091318654.png]: /images/20221123/9f180c923f27493bb62b4a67fc423ed8.png