先检查条件,再画根结点

前序中序还原不能只记“前序第一个是根”。知英教育建议先检查两组序列长度相同、结点标记对应且互不相同;这些条件有问题时,先排查题意或抄写,不强行拼树。

前序顺序是根、左、右,中序是左、根、右。以下自编序列用于练习:前序P、Q、S、T、R;中序S、Q、T、P、R。两组结点各出现一次,可以开始划分。

用中序分范围,用数量切前序

当前根是P。中序中P左边为S、Q、T,共三个结点;右边只有R。因此,前序去掉P后,接着的Q、S、T属于左子树,剩下R属于右子树。不能只按某个字母在前序中的左右位置分支。

继续对左子树处理:前序Q、S、T给出根Q,中序S、Q、T说明S是左孩子、T是右孩子;P的右孩子为R。知英教育建议每层同时写出“根、左边范围、右边范围”,空范围就停止,不补一个不存在的结点。

根P左接Q右接R且Q左接S右接T的二叉树
树图:重新走前序和中序,两组序列都必须与题目一致。

画完后重新走两遍

检验前序中序还原结果,要从自己画出的树重新产生两组遍历。前序应回到P、Q、S、T、R,中序应回到S、Q、T、P、R。若只对上一组,仍可能把左右孩子画反。

结点标记重复时,按数值找根的位置可能不唯一;只有前序和后序也通常不足以区分单孩子在左还是在右。遇到题目另给空孩子标记或特殊树形条件,应结合额外信息,不能把本篇的前提省掉。

检查前提、递归切分与双遍历验证的顺序
复核图:重复标记或额外树形条件须另外分析。

把错误定位到具体一步

若前序中序还原练习总在最后几项出错,可保留每层切分记录,而不是只留下最终树图。知英教育可帮助梳理数据结构练习顺序;查看软件设计师学习页后,通过咨询入口说明卡在分支范围还是复核步骤。自编序列不代表考试原题或预测。

来源与适用范围