接上一篇 “穿针引线法”读二叉树前中后序 ,初学二叉树还会碰到这类题型:给出前序中序或者后序中序,将二叉树还原出来。不会出现给前后序让画二叉树的,前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树。 故不能唯一确定一个二叉树。但是给了中序就确定了唯一二叉树,通常解法是采用逐步递归。看一下常规解法步骤:
前序+中序
- 根据前序序列的第一个元素建立根结点;
- 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
- 在前序序列中确定左右子树的前序序列;
- 由左子树的前序序列和中序序列建立左子树;
- 由右子树的前序序列和中序序列建立右子树。
后序+中序
- 根据后序序列的最后一个元素建立根结点;
- 在中序序列中找到该元素,确定根结点的左右子树的中序序列;
- 在后序序列中确定左右子树的后序序列;
- 由左子树的后序序列和中序序列建立左子树;
- 由右子树的后序序列和中序序列建立右子树。
这样耗费时间较长,有没有直观的方法呢?是有的。
口诀
给前序中序,前序从上往下写;
给后序中序,后序从下往上写;
怎么顺眼怎么画
来看个例子:
例题一:前序遍历:ABDXYCEGF 中序遍历:XDYBAGECF,画出二叉树,并求后序。
解题:写出前中序,注意前序要竖着写在左边,中序写在下面。再把对应的位置给标出来,连起来,就完成了:
例题二:中序遍历:BDCAEHGKF 后序遍历:DCBHKGFEA,画出二叉树,并求后序。
解题:写出后中序,注意后序( 后序从下向上写 )要竖着写在左边,中序写在下面。再把对应的位置给标出来,连起来,就完成了:
🛑用这个方法画出来的结果一定要结合我上一篇文章快速读二叉树来检验一下结果,防止出错!!!
先找根节点就行了,然后画子树(同样先找根节点)