2011年408统考数据结构第6题考的是二叉树遍历序列的还原与结点性质判定。题目问的是“无右孩子结点有几个”。这类题在408和各大高校数据结构的期末卷里出现频率都很高但很多考生第一步建树没问题最后却数错。问题往往出在分不清“无右孩子”和“叶子结点”的包含关系。今天这篇文章把先序中序、后序中序两种还原场景都讲透并给出可直接运行的Python代码帮你把这类题的分数稳定拿到手。先给一个可立刻上手的结论不管题目给的是“先序中序”还是“后序中序”只要按分治递归还原出二叉树再统计右指针为空的结点就能得到答案。关键是统计时不要只看叶子还要看只有左孩子、没有右孩子的结点。下面先用一道同型真题示例完整过一遍再讲快速判断技巧和避坑清单。这篇文章的核心不是背答案而是把“还原二叉树”和“统计无右孩子结点”这两个能力一次性固化下来。为了方便大家判断这篇内容值不值得读完文章会覆盖四个部分考点速览、手算还原、代码验证、考场提速。前两部分解决“会不会算”第三部分解决“算得对不对”第四部分解决“能不能在选择题里省时间”。如果你正在备考408或者正在复习数据结构期末建议把这篇文章当作一个完整的题型专题来刷不要只盯着最后的答案。1. 考点速览与核心能力1.1 考点定位“无右孩子结点有几个”这道题放在408大纲里属于树与二叉树模块核心考点是二叉树的遍历与性质。它不直接考背诵而是考两件事第一能不能根据给出的遍历序列还原出二叉树第二能不能准确理解“无右孩子”这个术语的边界。两个能力缺一个都容易出错。项目内容考点归属数据结构树与二叉树常见出题方式给出两种遍历序列求无右孩子结点个数核心方法分治递归还原二叉树再统计右指针为空的结点统计范围叶子结点 只有左孩子、没有右孩子的结点判断依据结点的右子树为空则该结点无右孩子必备前置先序、中序、后序遍历规则中序先序/后序能唯一确定二叉树高频易错点漏数叶子结点把无右孩子和无左孩子混为一谈先序/后序取根位置出错中序切割边界写错1.2 判断标准并不复杂很多同学看到“无右孩子”四个字第一反应是找二叉树中所有叶子结点。这个方向不完整。叶子结点的右指针确实是空的但“只有左孩子、右指针为空”的结点同样属于无右孩子。举个例子一棵树中有一个结点只有左孩子、没有右孩子它肯定不是叶子但它仍然是“无右孩子结点”。如果把这类结点漏掉统计结果就会偏小。因此做题时统一标准只有一条看右指针是否为空。右指针为空就计数右指针不为空就不计数。这个标准全程不变不需要额外记忆其他规则。唯一的难点在于还原二叉树的过程中你能不能准确判断每个结点右子树是否存在。判断方法也很直接在中序序列里当前根结点右侧还有元素就说明它有右子树右侧没有元素就说明没有右孩子。2. 题目定位与适用场景2.1 2011年第6题到底考什么2011年408统考真题数据结构部分第6题属于选择题中的常规难度题但它的陷阱设计很有代表性。题目本身并不要求写出完整的建树代码而是要求考生在有限时间内根据遍历序列还原出树的拓扑结构然后完成计数。这类题在408真题中反复出现只是问法会换有时问“无右孩子结点有几个”有时问“无左孩子结点有几个”有时问“叶子结点有几个”底层逻辑完全一样。由于官方原题的完整遍历序列在不同年份的回忆版中会有差异复习时更重要的是掌握这一类题的通法。本文示例选用了最经典的“先序中序”和“后序中序”组合只要把这两个组合练熟不管考试时拿到哪组序列都能快速套用。不要死记某道题的答案因为408命题组换一组序列结果就会完全不同。2.2 适合谁看不适合谁看这篇文章主要面向备考408的学生、准备数据结构期末考试的学生以及需要快速复习二叉树遍历算法的开发者。如果你在“给出先序和中序画不出树”这个阶段卡壳文章第4节会手把手带着你走一遍如果你已经能熟练建树可以直接跳到第7节学考场提速技巧用更短的时间完成统计。如果你正在准备机试或代码笔试这篇文章的代码部分可以当做一个基础模板使用。不过408统考选择题不写代码所以代码只是验证手算正确性的工具并不是考试必须掌握的写法。如果你已经完全不记得三种遍历的定义建议先花五分钟复习先序、中序、后序的概念再来读第4节否则分治过程会看得比较吃力。2.3 学习边界与内容范围本文只讨论“根据遍历序列还原二叉树并统计无右孩子结点”这一条主线不展开线索二叉树、平衡二叉树、哈夫曼树等扩展内容。这样做的好处是专注方便把易错点讲透。坏处也很明显如果你需要的是完整的数据结构知识体系这篇文章不能替代教材。建议把本文当作一个专题练习先掌握核心题型再回到教材去补其他树结构的知识。同时要说明本文所有代码都用于学习验证不涉及任何工程部署或接口调用。代码会给出基础的递归实现帮助你把抽象的分治过程落到可执行的程序上。考场上你不需要写这段代码但用代码验证过手算结果之后你对“还原二叉树”这个动作的理解会扎实很多。3. 前置知识三种遍历与二叉树还原3.1 三种遍历序列特征先序遍历的顺序是“根 - 左 - 右”所以先序序列的第一个元素一定是整棵树的根。中序遍历的顺序是“左 - 根 - 右”所以在中序序列中找到根后根左边一定是左子树的所有结点根右边一定是右子树的所有结点。后序遍历的顺序是“左 - 右 - 根”所以后序序列的最后一个元素一定是整棵树的根。这三句话是这个题型的全部理论基础。后面所有手算和代码都只是在反复使用“先序/后序找根中序分割左右子树”这一个逻辑。一旦理解了这一点就会发现“无右孩子结点有几个”这类题并不难难的是在递归过程中保持区间切割不越界。3.2 为什么必须结合中序序列先序和后序都能提供“根在哪里”的信息但单独靠其中一种无法确定左、右子树的范围。例如先序序列是“AB”你无法确定B是A的左孩子还是右孩子后序序列是“BA”同样无法确定。只有结合中序序列利用中序中根的位置划分左右子树才能唯一确定一棵二叉树。需要注意如果只给先序和后序而没有中序二叉树不一定唯一所以题目通常会给“中序先序”或“中序后序”的组合。做题时第一步永远是先在给出的两个序列中把中序序列单独挑出来准备用它做区间划分。这是防止思路混乱的关键操作。3.3 无右孩子结点的精确含义“无右孩子”指的是二叉树中某个结点的右指针为空也就是右子树不存在。它包含两种情况结点类型左子树右子树是否无右孩子叶子结点空空是只有左孩子的结点非空空是只有右孩子的结点空非空否左右孩子都有的结点非空非空否从表里能看出来判断“无右孩子”和判断“叶子结点”完全是两套标准。叶子结点一定是无右孩子结点但无右孩子结点不一定是叶子结点。做题时最容易错的就是把“只有左孩子、没有右孩子”的结点漏掉。后面代码的统计逻辑会严格按右指针是否为空来判断这样就不会漏。4. 典型同型题先序中序还原4.1 题目示例下面这道题与2011年第6题同型用它演示完整解题过程。已知一棵二叉树的先序遍历序列为A B D E C F中序遍历序列为D B E A C F求该二叉树中无右孩子结点的个数。先不要往下看自己拿张纸试着画一下然后再对答案。这样能更快暴露你是哪一步容易错是根找不准还是子树切分不对或是最后统计漏项。4.2 手算分步还原过程先序序列第一个元素是A所以根结点是A。在中序序列 D B E A C F 中找到AA左边是D B E构成左子树A右边是C F构成右子树。此时整棵树已经被分成三部分根A、左子树(D B E)、右子树(C F)。接下来处理左子树。左子树的中序序列是 D B E左子树的先序序列是原先序中A后面的 B D E。左子树的根是B因为先序序列 B D E 的第一个元素是B。在中序序列 D B E 中找到BB左边是D右边是E因此B的左孩子是D右孩子是E。到这里左子树已经完整D和E分别是叶子结点。再处理右子树。右子树的中序序列是 C F右子树的先序序列是原先序中左子树后面的 C F。右子树的根是C因为先序序列 C F 的第一个元素是C。在中序序列 C F 中找到CC左边没有元素右边是F因此C没有左孩子右孩子是F。F是叶子结点。整个还原过程可以整理成下面这张表子树根左子树右子树整棵树AD B EC FA的左子树BDEA的右子树C空FB的左子树D空空B的右子树E空空C的右子树F空空4.3 统计无右孩子结点还原完成后逐个检查每个结点的右孩子是否为空。A右孩子是C所以不是无右孩子。B右孩子是E所以不是无右孩子。C右孩子是F所以不是无右孩子。D没有右孩子计数1。E没有右孩子计数1。F没有右孩子计数1。最终无右孩子结点一共有3个分别是D、E、F。注意B和C都有右孩子所以不计数A也有右孩子同样不计数。这个例子比较简单所有无右孩子结点都是叶子。为了强化理解可以再看另一种情况如果题目问的是“无左孩子结点有几个”那么C、D、E、F四个结点都没有左孩子答案就会变成4。可见“左”和“右”的统计口径完全不同做题时一定要看清题干的字眼。4.4 为什么这个还原结果是唯一的在“先序中序”组合下每次递归都能确定当前子树的根并且中序序列能唯一划分左右子树所以整棵二叉树是唯一的。这个唯一性保证了统计结果不会出现歧义。有的同学担心自己画的二叉树不一样导致答案不同。只要严格按“先序第一个元素是根中序根左侧是左子树根右侧是右子树”来递归得到的树一定一样。如果遇到两个序列组合无法唯一确定二叉树的情况题目通常会给出额外条件比如“这是一棵完全二叉树”或者“这是二叉搜索树”。但在“无右孩子结点有几个”这道题里一般不会加入这些额外限制因为中序先序或中序后序已经足够唯一。5. 用代码验证递归建树与统计5.1 环境准备代码只需要Python 3.6以上版本不需要安装任何第三方库。可以在本机创建一个.py文件或直接在交互式环境里逐段执行。代码使用递归方式构造二叉树然后在树上统计无右孩子结点个数。递归边界条件是当前序列为空说明没有子树返回0。无论先序中序还是后序中序这个边界都不变。5.2 结点定义与建树函数先定义一个最简单的二叉树结点类每个节点包含一个值、左孩子指针、右孩子指针。然后用一个函数根据先序序列和中序序列构造二叉树。核心逻辑是先序第一个元素是根在中序中找到根的位置根左边是左子树右边是右子树然后递归构造左右子树。class TreeNode: def __init__(self, val): self.val val self.left None self.right None def build_tree(preorder, inorder): 根据先序序列和中序序列构造二叉树 if not preorder: return None root_val preorder[0] root TreeNode(root_val) idx inorder.index(root_val) left_len idx root.left build_tree(preorder[1:1 left_len], inorder[:idx]) root.right build_tree(preorder[1 left_len:], inorder[idx 1:]) return root这个函数最关键的是切割左右子树的区间。left_len表示左子树有多少个节点它等于根节点在中序序列中的下标。先序序列从第1个元素开始取left_len个作为左子树剩下的部分从第1 left_len个元素开始作为右子树。中序序列则直接用根节点的下标分割。只要区间写对递归就不会乱。5.3 统计函数与完整代码统计无右孩子节点的递归逻辑非常直观先看当前节点右指针是否为空为空就加1然后分别递归左子树和右子树。因为右指针为空时右子树不存在所以不会对右子树递归不会漏数也不会重复计数。def count_no_right_node(root): 统计二叉树中无右孩子结点的个数 if root is None: return 0 cnt 0 if root.right is None: cnt 1 cnt count_no_right_node(root.left) cnt count_no_right_node(root.right) return cnt preorder [A, B, D, E, C, F] inorder [D, B, E, A, C, F] root build_tree(preorder, inorder) print(count_no_right_node(root)) # 预期输出 3把这两段代码合并运行会输出3说明手算结果正确。如果你想看看建出来的树到底长什么样可以再写一个层序遍历或打印左右孩子的函数把每个节点的孩子信息打出来。这样能更直观地看到D、E、F三个叶子结点为什么被计数也能帮你验证自己画的树是否正确。5.4 后序中序的递归写法如果题目给的是后序序列和中序序列构造函数只需要把“根”从先序的第一个元素改成后序的最后一个元素。其他所有分治逻辑一模一样。下面的代码可以直接替换使用def build_tree_from_post(postorder, inorder): 根据后序序列和中序序列构造二叉树 if not postorder: return None root_val postorder[-1] root TreeNode(root_val) idx inorder.index(root_val) left_len idx root.left build_tree_from_post(postorder[:left_len], inorder[:idx]) root.right build_tree_from_post(postorder[left_len:-1], inorder[idx 1:]) return root postorder [D, E, B, F, C, A] inorder [D, B, E, A, C, F] root2 build_tree_from_post(postorder, inorder) print(count_no_right_node(root2)) # 预期输出 3这里要注意后序区间切割左子树的后序部分从开头取left_len个元素右子树的后序部分从第left_len个元素开始一直到倒数第二个元素为止。最后一个元素是整棵子树的根不能放进右子树。如果写成postorder[left_len:]就会把根节点包含进去递归时序列长度不会正确缩小程序最终会报错或算出错误结果。5.5 辅助函数生成三种遍历序列为了让自己出题练习可以写一组辅助函数先构造一棵二叉树然后输出先序、中序、后序序列再用上面的函数反向还原。这样既能验证手算也能增加对三种遍历顺序的熟悉度。def preorder_traversal(root): if root is None: return [] return [root.val] preorder_traversal(root.left) preorder_traversal(root.right) def inorder_traversal(root): if root is None: return [] return inorder_traversal(root.left) [root.val] inorder_traversal(root.right) def postorder_traversal(root): if root is None: return [] return postorder_traversal(root.left) postorder_traversal(root.right) [root.val]比如先用build_tree建一棵树再调用这三个函数输出序列就会发现preorder inorder或postorder inorder都能唯一还原出原来的树。这个方法特别适合考前自测自己设计一棵树打印遍历序列过一晚上再拿序列还原看能否得到同一棵树。6. 后序中序还原思路6.1 确定根的方式后序遍历的顺序是“左 - 右 - 根”因此后序序列的最后一个元素是整棵树的根。比如后序序列 D E B F C A 中最后一个元素是A所以根是A。找到中序序列 D B E A C F 中的A后A左侧是左子树右侧是右子树。这一步和先序版本类似区别只是从“第一个元素”换成了“最后一个元素”。6.2 实例分步还原后序序列D E B F C A中序序列D B E A C F。根是A。中序序列中A左边是 D B E构成左子树A右边是 C F构成右子树。左子树的后序序列从后序中截取属于左子树的元素这是 D E B。左子树的根是B因为 D E B 的最后一个元素是B。在中序序列 D B E 中B左边是D右边是E所以B的左孩子是D右孩子是E。右子树的后序序列是 F C右子树的根是C因为 F C 的最后一个元素是C。在中序序列 C F 中C左边为空右边是F所以C没有左孩子右孩子是F。还原出的二叉树与第4节完全一样因此无右孩子结点依然是D、E、F三个。从这个例子可以看出先序中序和后序中序两种组合只要中序相同、树相同统计结果必然相同。考试时无论遇到哪种组合方法都不变。6.3 切割边界特别提醒后序版本的常见错误是取根时取了后序的第一个元素或者切割右子树时把根元素也包含进去。实际上后序序列的结构是“左子树后序 右子树后序 根”切分右子树时要用postorder[left_len:-1]不能写成postorder[left_len:]。一旦包含根后续递归会把根重复当成右子树节点不仅树结构错乱统计结果也会完全不对。另外要注意在后序中序的分治中左子树的序列长度依然由“根在中序中的下标”决定。因为中序里根左边有几个元素左子树就有几个节点这个数量与后序无关。只要坚持“先找根再算左子树长度最后切分两个序列”就不容易出错。7. 考场快速统计法与伪代码7.1 为什么不用画出完整树在考场上如果每道题都画完整棵树速度会慢而且图画得越大越容易看错。实际上统计无右孩子结点可以在分治过程中直接完成。每当我们确定一个子树根节点时只要看一眼这个根节点在中序序列中的右侧是否还有元素就能判断它有没有右孩子如果右侧为空说明该根节点无右孩子如果右侧有元素说明有右孩子。因为中序序列的顺序是“左子树、根、右子树”根节点右侧的元素全部来自右子树。7.2 分治计数伪代码下面这段伪代码没有真正构造二叉树而是把“当前根节点是否无右孩子”的信息直接累加进计数器。它的输出与建树统计完全一致运行第4节的例子也会得到3。def count_no_right_fast(preorder, inorder): if not preorder: return 0 root_val preorder[0] idx inorder.index(root_val) left_len idx # 当前根节点右边没有元素说明没有右子树计数1 cnt 1 if idx len(inorder) - 1 else 0 cnt count_no_right_fast(preorder[1:1 left_len], inorder[:idx]) cnt count_no_right_fast(preorder[1 left_len:], inorder[idx 1:]) return cnt这个函数把建树和统计合并成了一个过程节省了空间也避免画图带来的视觉干扰。对熟手来说用这段代码的思路口算速度会明显更快。如果你在考场上不习惯写伪代码也可以把这个逻辑转换成表格记录每次递归得到的根节点以及中序中该根节点右侧是否为空。7.3 口算五步法第一步找到根。先序中第一个元素就是根后序中最后一个元素就是根。第二步在中序中定位根根左侧为左子树右侧为右子树。第三步判断这个根节点在中序中右侧是否为空如果为空计数器加1。第四步对左子树重复上述过程。第五步对右子树重复上述过程。整个过程不需要把整棵树画出来只需要记住每次递归的根节点索引。如果用第4节的例子来练根A在中序中右侧有C、F所以A不算左子树根B在中序中右侧有E不算D和E作为子树根时右侧都为空计数两个右子树根C在中序中右侧有F不算F作为子树根时右侧为空计数一个。最后得到3。这个口算过程熟练后20秒内就能完成。7.4 不同遍历组合的规则对比遍历组合根在哪里中序中的作用右子树切割参考先序中序先序第一个元素根左侧是左子树右侧是右子树先序中根后面left_len个元素后序中序后序最后一个元素根左侧是左子树右侧是右子树后序中倒数第left_len个元素之前中序层序层序第一个出现的节点作为当前子树根根左侧是左子树右侧是右子树需要额外记录层序节点集合8. 考场常见错误与排查8.1 高频错误对照表错误现象可能原因修正方法统计结果少算叶子结点只统计了非叶子结点中右指针为空的结点叶子结点左右指针都为空也属于无右孩子结点统计结果多算“只有左孩子”的结点误以为“无右孩子”等于“叶子结点”明确无右孩子只与右指针有关与左孩子是否存在无关先序中序时取根取错用了中序第一个元素作为根先序第一个元素是根中序第一个元素只是最左结点后序中序时取根取错用了后序第一个元素作为根后序最后一个元素是根第一个元素是最左子树的叶子中序分割边界错误把根也放进了左子树或右子树根左边是左子树右边是右子树根本身不参与子树递归后序切割右子树时把根包含进来切分区间写错右子树后序应该用postorder[left_len:-1]不确定根节点是否有右孩子只画了根节点没有看中序右侧区间中序中根节点右边为空则该节点无右孩子空树被算了1次把空指针当作无右孩子结点只有实际存在的结点才参与统计这张表可以在做题前快速过一遍。如果你发现自己总是在某类题目上反复出错先对照表定位是“取根”的错误还是“分割”的错误再针对性地刷2到3道同型题效果比盲目刷题好很多。8.2 如何通过选项反推如果选择题选项给的是数字比如“1、2、3、4”你可以先根据中序序列中根节点的右侧是否为空排除一部分选项。比如一棵树中至少有一个叶子结点而无右孩子结点的个数一定大于等于叶子结点的个数所以选项如果给出的数字比叶子结点数还少一定错误。另外无右孩子结点的个数不会超过总结点数。如果一棵二叉树有6个结点选项出现“6”或“7”基本可以直接排除。因为根节点如果也有右孩子那么至少有一个结点有右孩子无右孩子结点数最多是5。这类排除法虽然不能直接得到答案但能帮你减少计算量。8.3 专项练习建议建议每天刷3道“根据遍历序列还原二叉树”的题目每种组合各一道。刷的时候不要着急写代码先手算再写代码验证。手算训练的是“递归分割”的熟练度代码验证训练的是逻辑严谨性。两周后这道题的解题速度会有明显提升。9. 实战自测题与答案9.1 自测题一已知一棵二叉树的先序遍历序列为 A B C D E中序遍历序列为 C B A D E求该二叉树中无右孩子结点的个数。建议先自己手算再往下看答案。9.2 自测题一解析先序序列第一个元素是A所以根是A。中序序列 C B A D E 中A左边是 C B属于左子树A右边是 D E属于右子树。左子树的先序序列是 B C中序序列是 C B。左子树根是B中序中B左边是C右边为空所以B有左孩子C无右孩子计数1。右子树的先序序列是 D E中序序列是 D E。右子树根是D中序中D左边为空右边是E所以D无左孩子有右孩子E。E是叶子计数1。C是叶子计数1。最终答案是3。9.3 自测题二已知一棵二叉树的中序遍历序列为 D B E A C F后序遍历序列为 D E B F C A求无右孩子结点的个数。这道题就是第6节的实例答案还是3。如果能在20秒内写出计数过程说明已经掌握了分治快速统计法如果不能建议重新看一遍第6节和第7节。9.4 自测题三已知一棵二叉树的先序遍历序列为 A B C D E F G中序遍历序列为 C B D A F E G求无右孩子结点的个数。这道题多加了一个结点需要仔细切割左右子树。答案是根A左子树由 C B D 组成右子树由 F E G 组成。左子树根B中序中B左边C右边D所以B有左右孩子C和D都是叶子计数2。右子树根E中序中E左边F右边G所以E有左右孩子F和G都是叶子计数2。最终答案是4。10. 总结与下一步2011年第6题这类“无右孩子结点”题目最值得掌握的不是某道具体题的答案而是“先序/后序定根中序分割子树”的分治框架。最先要验证的能力是拿到一组先序中序序列能否在30秒内确定根的位置并判断每个根节点是否有右孩子。最容易踩的坑是漏掉叶子结点和“只有左孩子”的结点以及后序切割时把根包含进去。如果你正在备考408建议把今天的方法手写在笔记本上之后连续刷3到5道同型题直到形成肌肉记忆。代码部分可以保留成一个Python脚本遇到自定义二叉树时先生成遍历序列再用代码反向还原验证自己的手算结果。后续还可以继续扩展的方向包括已知中序层序还原二叉树、二叉树线索化、根据遍历序列判断某一结点有无右兄弟等。这些考点本质相同都是分治思想的变体。建议收藏备用考前一晚再快速过一遍易错表。