一道面试题快速梳理二叉树知识

痛定思痛。 2023-07-12 14:51 7阅读 0赞

题目如下：大家先简单思考一下

> 已知二叉树的前序序列为BCDEFAG，中序序列为DCFAEGB，请问后序序列为\_\_\_  
> A. DAFEGCB  
> B. DAEGFCB  
> C. DAFGECB  
> D. DAEFGCB

> 思路：通过已知前序序列和中序序列，画出二叉树，即可得出后序序列。

这里咱们先提一下：`前序`、`中序`、`后序`的区别，方便分析。

*  前序：根节点=》左节点=》右节点
 *  中序：左节点=》根节点=》右节点
 *  后序：左节点=》右节点=》根节点

下面看个小例子先理解下区别：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70]

前序：ABC
    中序：BAC
    后序：BCA

到了这里，前中后序已经区分了，接下来根据已知条件，画出二叉树，这道题就迎刃而解了。

分析：

1.  首先，它的前序序列为BCDEFAG。再来回忆下前序（根，左，右），由此可以看出B为根节点，C为左节点，而D的情况有些特殊，D可能在C的右侧，也有可能在C节点下的左右节点，如下图
    
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 1]
2.  然后看它的中序序列为DCFAEGB，再来回忆下中序（左，根，右）。上面已经分析出来B为根节点，那么根据中序特点，可以发现DCFAEG都是左节点的，由此可以排除图1的情况，接下来再看下中序序列，序列中的DC说明D是左节点，排除图3的情况。
3.  其次再看下前序序列BCDEFAG，结合图2，可以看出E为C的右节点，而前序是根，左，右。说明E是C的右节点如图4。再根据中序序列DCFAEGB和中序特点（左，根，右）及E为根节点，可以推出F，A节点是E的左节点，此时有两种情况，如图5和图6。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 2]
4.  最后根据前序序列BCDEFAG，再来回忆下前序（根，左，右），上面已经知道F，A都为E的左节点，根据前序特点，可以排除图6。根据中序序列DCFAEGB和F，A是左节点，推出G为E的右节点，最后完整的二叉树如图7。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 3]

> 最后看图得出后序序列：DAFGECB

如果觉得不错的，请帮忙点个赞！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200309144028425.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200309150057109.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200309154826638.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200309160605561.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc0MDUzMA==,size_16,color_FFFFFF,t_70