考研408真题里有一道很容易被小看的题2011年第6题数据结构中的二叉树考点问的是“无右孩子结点有几个”。不少考生第一次做这道题会把“无右孩子”当成“叶子结点”的另一种说法。实际上这俩概念并不等价差在“有左孩子但没有右孩子”的一度结点上。这道题之所以经典恰恰在于它把二叉树的性质、完全二叉树的结构、结点的编号规律几个知识点串在了一起。如果你正在复习408的数据结构部分或者刷题时在这道题上栽过跟头这篇就把它的推导过程、快速计算方法、以及考场上容易踩的坑一次讲清楚。1. 先弄清这道题到底在考什么1.1 “无右孩子结点”的定义和构成在二叉树中判断一个结点有没有右孩子本质就是看它的右子树是否为空。按照这个定义无右孩子结点包含两类。第一类是叶子结点。叶子结点的左右孩子都为空自然没有右孩子。第二类是只有左孩子、没有右孩子的结点。这类结点的度是1而且它的唯一孩子是左孩子。这里要特别强调一点度为1的结点既可能是“只有左孩子”也可能是“只有右孩子”。只有左孩子而没有右孩子的结点才属于无右孩子结点只有右孩子而没有左孩子的结点是有右孩子的不能算进去。可以用二叉树的基本公式辅助理解。设一棵二叉树的叶子结点数为 n0度为1的结点数为 n1度为2的结点数为 n2总结点数为 n。那么有n n0 n1 n2同时二叉树的边数等于 n - 1而边数也可以写成 n1 2n2。于是可以推出n0 n2 1这个关系式本身没有直接给出无右孩子结点数但它说明了一个重要事实单靠“总结点数和叶子结点数”你没法唯一确定无右孩子结点的数量。因为 n1 中到底是有左无右还是有右无左题目不给出额外条件是推不出来的。所以凡是要计算无右孩子结点的题目一定会补一个条件。最常见的是补“完全二叉树”或者给你前序和中序、后序和中序的遍历序列。2011年第6题采用的是前一种方式。1.2 为什么2011年这道题容易出错这道题在当年的选择题里错误率不算低主要原因是三个“想当然”。第一个想当然是把“无右孩子结点”直接换成了“叶子结点”。如果题目问的是普通二叉树这两个数确实可能相等但前提是不存在“有左无右”的结点。2011年第6题碰巧满足了这个条件所以答案和叶子结点数恰好一致。但很多人在概念层面就把两者合并了后面刷到偶数个结点或非完全二叉树的变型题时就会漏算。第二个想当然是把“完全二叉树”当成了“满二叉树”。完全二叉树只要求最后一层靠左连续不需要每一层都满。2011个结点显然不是满二叉树因为满二叉树的结点数必须是 2^k - 1。如果按满二叉树去套整道题的推导方向都会偏。第三个想当然是觉得结点总数是2011一定比较难算。其实这类题真正要处理的不是2011这个数本身而是它除以2之后的奇偶情况。2011是奇数这个属性很关键。总结点数为奇数时完全二叉树的最后一个非叶结点左右双全不存在“有左无右”的结点总结点数为偶数时才可能出现一个特殊结点。把这三点想清楚了考点就很清晰它不是考复杂计算而是考你是否真的懂完全二叉树的结构编号规律。2. 2011年第6题完全二叉树中“无右孩子结点”的推导2.1 先还原题目的核心场景2011年这道真题常见的整理版本是已知一棵完全二叉树共有2011个结点求这棵二叉树中无右孩子结点的个数。也有资料会把提问写成“叶子结点的个数”。这两种问法在数值上经常一样但概念上不能混。本文统一按“无右孩子结点”来展开你拿着两种问法去对答案都能对得上。先复习完全二叉树的编号规律。把根结点编号为1从上到下、从左到右编号。对任意编号为 i 的结点如果 2i 小于等于 n它存在左孩子左孩子编号是 2i。如果 2i 1 小于等于 n它存在右孩子右孩子编号是 2i 1。它的父结点编号是 ⌊i / 2⌋。这个规律是解决所有完全二叉树问题的根基。2011年第6题的结果完全可以由这套编号规律推出来不需要背特殊公式。2.2 分步解法从2011个结点推出结构第一步算出最后一个非叶子结点的编号。叶子结点的特征是 2i 大于 n也就是 i 大于 n/2。所以叶子结点的编号从 ⌊n/2⌋ 1 开始最后一个非叶子结点的编号就是 ⌊n/2⌋。当 n 2011 时⌊2011 / 2⌋ 1005所以编号1005是最后一个非叶子结点。第二步判断编号1005的结点有没有右孩子。它的左孩子编号是 2 × 1005 2010右孩子编号是 2 × 1005 1 2011。2010和2011都没有超过 n说明编号1005的结点同时拥有左孩子和右孩子。第三步数叶子结点。编号1006到2011的结点都是叶子结点。因为它们的 2i 都大于2011不可能再有孩子。叶子结点数计算如下2011 - 1005 1006第四步判断是否存在“有左无右”的结点。在完全二叉树中除了最后一个非叶子结点之外其他非叶子结点如果存在都一定是左右双全的。原因是完全二叉树上面每一层都是满的只有最后一层可能不满而最后一个非叶子结点的孩子正好处在最后一层。所以只需要检查编号1005这一个结点即可。现在编号1005既有左孩子又有右孩子因此整棵树不存在“有左无右”的结点。第五步汇总。无右孩子结点数 叶子结点数 有左无右结点数 1006 0 1006。2.3 验证答案用更小的完全二叉树找规律如果考场上你不敢确定结论可以用一个小规模的完全二叉树验证再把规律推广到 n 2011。以 n 6 为例。6个结点的完全二叉树结构是根结点1有左孩子2和右孩子3结点2有左孩子4和右孩子5结点3只有左孩子6没有右孩子结点4、5、6是叶子。叶子结点是4、5、6共3个。有左无右的结点只有3号共1个。所以无右孩子结点一共4个。这里的4等于叶子结点数3加上1。而 n 6 是偶数。再看 n 5叶子结点数是3且不存在有左无右的结点所以无右孩子结点数是3。从 n 5 和 n 6 这两个小例子就能看出规律完全二叉树的无右孩子结点数在总结点数为奇数时等于 ⌈n/2⌉在总结点数为偶数时还要再加1。n 2011 是奇数所以答案是1006。这种“先画小树、找规律、再代入大数”的方法在考场上比死记公式更可靠。3. 更一般的二叉树从遍历序列判断无右孩子结点完全二叉树的问法只是其中一种。408真题里还有一类变形题给出一棵普通二叉树的前序和中序序列或者后序和中序序列让你判断无右孩子结点有几个。这里讲一下通用处理方式。3.1 前序中序的组合怎么数前序遍历顺序是“根、左、右”中序遍历顺序是“左、根、右”。处理这类题我一般分三步走。第一步取前序序列的第一个元素它就是当前二叉树的根。第二步在中序序列中找到这个根。中序序列里根左边的部分属于左子树右边的部分属于右子树。第三步根据左右子树的中序序列长度把前序序列里剩下的部分切成两段分别对应左子树和右子树的前序序列然后递归处理。下面用一个示例演示不是真题原题但结构完全符合408的命题风格。假设前序序列是A B D E C F 中序序列是D B E A F C前序第一个是A所以A是根。中序里A左边是“D B E”右边是“F C”。左子树的中序是“D B E”对应的前序片段是“B D E”。B是左子树的根。B在中序里左边是D右边是E所以B的左孩子是D右孩子是E。右子树的中序是“F C”对应的前序片段是“C F”。C是右子树的根。C在中序里左边是F右边为空所以C的左孩子是F右孩子为空。还原出的树结构是A的左孩子是B右孩子是CB的左孩子是D右孩子是EC的左孩子是F没有右孩子。现在数无右孩子结点C有左孩子但没右孩子算一个D、E、F都是叶子算三个。总共4个。这里最容易漏掉的就是C。C不是叶子但它确实没有右孩子。如果只数叶子会得到3直接漏掉1个。3.2 后序中序的组合怎么数后序遍历顺序是“左、右、根”。处理思路和前序中序类似只是根的位置变成了后序序列的最后一个元素。继续用一棵等价树演示。假设中序序列是D B E A F C 后序序列是D E B F C A第一步后序最后一个元素是AA就是整棵树的根。在中序里A左边是“D B E”右边是“F C”。第二步左子树的后序序列是“D E B”。B是左子树的根。B在中序里左边是D右边是E所以B的左孩子是D右孩子是E。第三步右子树的后序序列是“F C”。C是右子树的根。C在中序里左边是F右边为空所以C的左孩子是F右孩子为空。还原结果和前序中序那棵树完全一样。后序中序的难点在于你处理右子树时后序序列要从后往前找根很容易把层次搞混。我的建议是每次找到根之后先在草稿纸上用括号把中序序列的左右区间框出来再根据区间长度截取后序片段不要光在脑子里推。把树还原出来之后无右孩子结点数还是4。这个例子也说明一个问题前序后序的组合不能唯一确定二叉树所以真题里如果给的是前序后序一般不会问“无右孩子结点有几个”只要给的是含中序的组合还原树并计数就是标准路径。4. 快速公式与边界条件为什么偶数和奇数结果不一样4.1 无右孩子结点数量的通式先给一般公式。对于任意二叉树无右孩子结点数 叶子结点数 只有左孩子没有右孩子的一度结点数。这个公式不针对某一道题而是所有“无右孩子”问题的基础。如果题目只说“这是一棵二叉树有 n 个结点”那么无右孩子结点数不能唯一确定。因为只靠 n你无法区分那些一度结点到底是有左无右还是有右无左。举例来说n 2 时如果根只有左孩子那么叶子1个、根也无右孩子总数是2如果根只有右孩子那么叶子1个、根有右孩子总数只有1。同样 n 2结果不一样。所以这类题必须有额外条件。4.2 完全二叉树中偶数和奇数的边界差异当题目指定为完全二叉树时情况就会收敛得非常清楚。完全二叉树的一个重要特征是除了最后一个非叶子结点其他非叶子结点如果存在都是左右双全。最后一层的结点全部靠左排列才可能导致一个特殊结点存在。设 n 为总结点数最后一个非叶子结点的编号是 ⌊n/2⌋。如果 n 是奇数那么2 × ⌊n/2⌋ 1 n也就是说最后一个非叶子结点的右孩子编号正好等于 n它是有右孩子的。既然它有右孩子整棵树就不存在“有左无右”的结点。此时无右孩子结点数 叶子结点数 n - ⌊n/2⌋ ⌈n/2⌉如果 n 是偶数那么2 × ⌊n/2⌋ 1 n 1这个值大于 n说明编号 n/2 的结点只有左孩子 n没有右孩子 n 1。于是这棵树里存在且只存在一个“有左无右”的结点编号是 n/2。此时无右孩子结点数 叶子结点数 1 (n - n/2) 1 n/2 1把两种情况合并起来就是下面这张表总结点数 n无右孩子结点数说明奇数⌈n/2⌉不存在有左无右结点偶数n/2 1编号 n/2 的结点有左无右4.3 这个公式在考场上的简化使用考场上拿到完全二叉树题目我的处理顺序是三步。第一步看 n 的奇偶性。第二步计算 ⌈n/2⌉。第三步如果 n 是偶数答案在 ⌈n/2⌉ 基础上加1如果 n 是奇数答案就是 ⌈n/2⌉。以 n 2011 为例它是奇数⌈2011/2⌉ 1006答案就是1006。这个流程十几秒就能走完。但要注意这套快速公式只能用在完全二叉树上。如果题目变成“一棵普通二叉树有2011个结点其中有……”这样的问法就必须结合更多条件比如叶子数、一度结点分布或者遍历序列不能直接套。5. 考场上的判断顺序和易错点清单5.1 判断顺序做题时不要急着代公式先用30秒把题目类型定下来。我的判断顺序如下。第一步确认题目给的二叉树类型。完全二叉树、满二叉树、普通二叉树、线索二叉树这四种情况处理方式完全不一样。第二步如果是完全二叉树算出最后一个非叶子结点编号 ⌊n/2⌋再判断它有没有右孩子。第三步求出叶子结点数。叶子编号从 ⌊n/2⌋ 1 到 n个数是 n - ⌊n/2⌋。第四步检查有没有有左无右的结点。只有 n 为偶数时才可能存在而且那个结点编号是 n/2。第五步把第三步和第四步的结果相加。第六步重新读一遍题干确认问的是“无右孩子结点”而不是“叶子结点”或者“无左孩子结点”。这三个问题答案可能不同。5.2 易错点结合长期做题的经验我总结出下面几个高频错误。第一把“无右孩子”和“叶子结点”混为一谈。叶子结点一定是无右孩子结点但无右孩子结点不一定是叶子结点。有左无右的非叶子结点在各类遍历题和带边界条件的树里都会出现。第二对完全二叉树只算叶子忘了检查 n 的奇偶性。n 是偶数时一定存在一个有左无右的结点这个结点不是叶子必须额外加进去。第三把完全二叉树当满二叉树处理。满二叉树要求每层都满完全二叉树只要求最后一层靠左连续。2011个结点连满二叉树应有的 2^k - 1 这个条件都满足不了不能用满二叉树公式去推。第四计算叶子结点数时用 n/2 而不是 ⌈n/2⌉。对 n 2011 来说n/2 等于1005.5四舍五入后是1006结果碰巧对但一旦 n 为偶数这种粗略处理就会出错。公式应该记成 n - ⌊n/2⌋ 或 ⌈n/2⌉。第五还原普通二叉树时只看遍历序列里的根不标注左右子树区间导致递归层次混乱。尤其是后序中序这种组合从后往前找根时很容易看串。5.3 检查方法算完答案之后可以用一组关系做完整性检查。对一棵二叉树设总结点数为 n有右孩子结点数 无右孩子结点数 n其中有右孩子结点数等于每个有右孩子的结点都数一次。在完全二叉树中如果 n 是奇数从编号1到 ⌊n/2⌋ 的所有结点都有右孩子所以有右孩子结点数是 ⌊n/2⌋。无右孩子结点数就是 n - ⌊n/2⌋。n 2011 时有右孩子结点数1005无右孩子结点数1006加起来正好等于2011。也可以用抽样验证先拿 n 5、n 6 这种小规模完全二叉树手算一遍如果总结出来的计数规律和小规模结果一致再代入大数。这个方法最适合考场紧张状态下的自查。最后再提醒一次考场上写完答案前把题干最后几个字重新读一遍。很多时候不是不会算而是把“无右孩子”看成了“无左孩子”或者把“无右孩子结点个数”看成了“叶子结点个数”。6. 同类题怎么练围绕“无右孩子”的扩展考点6.1 线索二叉树中的“无右孩子指针”“无右孩子结点”这个考点在408里还会和线索二叉树结合。中序线索二叉树中如果一个结点没有左孩子左指针指向前驱结点如果一个结点没有右孩子右指针指向后继结点。所以无右孩子结点的右指针会被线索化为中序后继。换句话说你看到的“右指针”不再是孩子而是一条线索。题目如果问“有多少右指针被线索化”本质上还是在问无右孩子结点的个数。复习线索二叉树时关键要区分两种指针状态正常右孩子指针和线索化右指针。判断标准就是看这个结点有没有右孩子。这和2011年第6题里用的是同一条判断逻辑。6.2 完全二叉树相关的其他公式既然2011年第6题把完全二叉树当作载体复习时可以顺手把下面这些结论一起掌握。这些结论彼此连通不要孤立记。叶子结点数n0 n - ⌊n/2⌋度为1的结点数n 为奇数时n1 0。 n 为偶数时n1 1此时 n/2 号结点只有左孩子。度为2的结点数n 为奇数时n2 (n - 1) / 2。 n 为偶数时n2 n / 2 - 1。树的高度对于含 n 个结点的完全二叉树高度 h ⌈log2(n 1)⌉。这些公式之间是连通的。用的时候可以结合一棵 n 6 的小树来验证不要死记。6.3 推荐复习路径如果你现在才开始集中突破“树”这一章建议按下面顺序来。第一先把二叉树的度、边数、结点数关系推明白。重点是 n0 n2 1 的来源以及 n n0 n1 n2 这个恒等式。第二把完全二叉树的编号规则和几个公式推导一遍。用 n 5 到 n 8 几棵小树手动画一遍比自己看十遍书都有效。第三把前序中序、后序中序还原树的方法练熟。408真题里给出中序序列的题目最终多半要落到重建树或判断某个结点位置这一步。第四遇到“无右孩子”“无左孩子”“叶子结点”“度为零的结点”这类字眼时先在草稿纸上写出各自的集合再看它们的交集和并集关系。刷题时养成这个习惯判断起来会快很多。最后提一个复习建议像2011年第6题这种题不要只记答案1006也不要把公式背下来就完事。真正考场上有用的是那套判断流程——先确认树型再算叶子再查有左无右最后相加。踩过一次坑之后就会发现这类题不是考计算是考你有没有把二叉树的结构真正理解透彻。
考研408真题解析：完全二叉树无右孩子结点个数如何计算
考研408真题里有一道很容易被小看的题2011年第6题数据结构中的二叉树考点问的是“无右孩子结点有几个”。不少考生第一次做这道题会把“无右孩子”当成“叶子结点”的另一种说法。实际上这俩概念并不等价差在“有左孩子但没有右孩子”的一度结点上。这道题之所以经典恰恰在于它把二叉树的性质、完全二叉树的结构、结点的编号规律几个知识点串在了一起。如果你正在复习408的数据结构部分或者刷题时在这道题上栽过跟头这篇就把它的推导过程、快速计算方法、以及考场上容易踩的坑一次讲清楚。1. 先弄清这道题到底在考什么1.1 “无右孩子结点”的定义和构成在二叉树中判断一个结点有没有右孩子本质就是看它的右子树是否为空。按照这个定义无右孩子结点包含两类。第一类是叶子结点。叶子结点的左右孩子都为空自然没有右孩子。第二类是只有左孩子、没有右孩子的结点。这类结点的度是1而且它的唯一孩子是左孩子。这里要特别强调一点度为1的结点既可能是“只有左孩子”也可能是“只有右孩子”。只有左孩子而没有右孩子的结点才属于无右孩子结点只有右孩子而没有左孩子的结点是有右孩子的不能算进去。可以用二叉树的基本公式辅助理解。设一棵二叉树的叶子结点数为 n0度为1的结点数为 n1度为2的结点数为 n2总结点数为 n。那么有n n0 n1 n2同时二叉树的边数等于 n - 1而边数也可以写成 n1 2n2。于是可以推出n0 n2 1这个关系式本身没有直接给出无右孩子结点数但它说明了一个重要事实单靠“总结点数和叶子结点数”你没法唯一确定无右孩子结点的数量。因为 n1 中到底是有左无右还是有右无左题目不给出额外条件是推不出来的。所以凡是要计算无右孩子结点的题目一定会补一个条件。最常见的是补“完全二叉树”或者给你前序和中序、后序和中序的遍历序列。2011年第6题采用的是前一种方式。1.2 为什么2011年这道题容易出错这道题在当年的选择题里错误率不算低主要原因是三个“想当然”。第一个想当然是把“无右孩子结点”直接换成了“叶子结点”。如果题目问的是普通二叉树这两个数确实可能相等但前提是不存在“有左无右”的结点。2011年第6题碰巧满足了这个条件所以答案和叶子结点数恰好一致。但很多人在概念层面就把两者合并了后面刷到偶数个结点或非完全二叉树的变型题时就会漏算。第二个想当然是把“完全二叉树”当成了“满二叉树”。完全二叉树只要求最后一层靠左连续不需要每一层都满。2011个结点显然不是满二叉树因为满二叉树的结点数必须是 2^k - 1。如果按满二叉树去套整道题的推导方向都会偏。第三个想当然是觉得结点总数是2011一定比较难算。其实这类题真正要处理的不是2011这个数本身而是它除以2之后的奇偶情况。2011是奇数这个属性很关键。总结点数为奇数时完全二叉树的最后一个非叶结点左右双全不存在“有左无右”的结点总结点数为偶数时才可能出现一个特殊结点。把这三点想清楚了考点就很清晰它不是考复杂计算而是考你是否真的懂完全二叉树的结构编号规律。2. 2011年第6题完全二叉树中“无右孩子结点”的推导2.1 先还原题目的核心场景2011年这道真题常见的整理版本是已知一棵完全二叉树共有2011个结点求这棵二叉树中无右孩子结点的个数。也有资料会把提问写成“叶子结点的个数”。这两种问法在数值上经常一样但概念上不能混。本文统一按“无右孩子结点”来展开你拿着两种问法去对答案都能对得上。先复习完全二叉树的编号规律。把根结点编号为1从上到下、从左到右编号。对任意编号为 i 的结点如果 2i 小于等于 n它存在左孩子左孩子编号是 2i。如果 2i 1 小于等于 n它存在右孩子右孩子编号是 2i 1。它的父结点编号是 ⌊i / 2⌋。这个规律是解决所有完全二叉树问题的根基。2011年第6题的结果完全可以由这套编号规律推出来不需要背特殊公式。2.2 分步解法从2011个结点推出结构第一步算出最后一个非叶子结点的编号。叶子结点的特征是 2i 大于 n也就是 i 大于 n/2。所以叶子结点的编号从 ⌊n/2⌋ 1 开始最后一个非叶子结点的编号就是 ⌊n/2⌋。当 n 2011 时⌊2011 / 2⌋ 1005所以编号1005是最后一个非叶子结点。第二步判断编号1005的结点有没有右孩子。它的左孩子编号是 2 × 1005 2010右孩子编号是 2 × 1005 1 2011。2010和2011都没有超过 n说明编号1005的结点同时拥有左孩子和右孩子。第三步数叶子结点。编号1006到2011的结点都是叶子结点。因为它们的 2i 都大于2011不可能再有孩子。叶子结点数计算如下2011 - 1005 1006第四步判断是否存在“有左无右”的结点。在完全二叉树中除了最后一个非叶子结点之外其他非叶子结点如果存在都一定是左右双全的。原因是完全二叉树上面每一层都是满的只有最后一层可能不满而最后一个非叶子结点的孩子正好处在最后一层。所以只需要检查编号1005这一个结点即可。现在编号1005既有左孩子又有右孩子因此整棵树不存在“有左无右”的结点。第五步汇总。无右孩子结点数 叶子结点数 有左无右结点数 1006 0 1006。2.3 验证答案用更小的完全二叉树找规律如果考场上你不敢确定结论可以用一个小规模的完全二叉树验证再把规律推广到 n 2011。以 n 6 为例。6个结点的完全二叉树结构是根结点1有左孩子2和右孩子3结点2有左孩子4和右孩子5结点3只有左孩子6没有右孩子结点4、5、6是叶子。叶子结点是4、5、6共3个。有左无右的结点只有3号共1个。所以无右孩子结点一共4个。这里的4等于叶子结点数3加上1。而 n 6 是偶数。再看 n 5叶子结点数是3且不存在有左无右的结点所以无右孩子结点数是3。从 n 5 和 n 6 这两个小例子就能看出规律完全二叉树的无右孩子结点数在总结点数为奇数时等于 ⌈n/2⌉在总结点数为偶数时还要再加1。n 2011 是奇数所以答案是1006。这种“先画小树、找规律、再代入大数”的方法在考场上比死记公式更可靠。3. 更一般的二叉树从遍历序列判断无右孩子结点完全二叉树的问法只是其中一种。408真题里还有一类变形题给出一棵普通二叉树的前序和中序序列或者后序和中序序列让你判断无右孩子结点有几个。这里讲一下通用处理方式。3.1 前序中序的组合怎么数前序遍历顺序是“根、左、右”中序遍历顺序是“左、根、右”。处理这类题我一般分三步走。第一步取前序序列的第一个元素它就是当前二叉树的根。第二步在中序序列中找到这个根。中序序列里根左边的部分属于左子树右边的部分属于右子树。第三步根据左右子树的中序序列长度把前序序列里剩下的部分切成两段分别对应左子树和右子树的前序序列然后递归处理。下面用一个示例演示不是真题原题但结构完全符合408的命题风格。假设前序序列是A B D E C F 中序序列是D B E A F C前序第一个是A所以A是根。中序里A左边是“D B E”右边是“F C”。左子树的中序是“D B E”对应的前序片段是“B D E”。B是左子树的根。B在中序里左边是D右边是E所以B的左孩子是D右孩子是E。右子树的中序是“F C”对应的前序片段是“C F”。C是右子树的根。C在中序里左边是F右边为空所以C的左孩子是F右孩子为空。还原出的树结构是A的左孩子是B右孩子是CB的左孩子是D右孩子是EC的左孩子是F没有右孩子。现在数无右孩子结点C有左孩子但没右孩子算一个D、E、F都是叶子算三个。总共4个。这里最容易漏掉的就是C。C不是叶子但它确实没有右孩子。如果只数叶子会得到3直接漏掉1个。3.2 后序中序的组合怎么数后序遍历顺序是“左、右、根”。处理思路和前序中序类似只是根的位置变成了后序序列的最后一个元素。继续用一棵等价树演示。假设中序序列是D B E A F C 后序序列是D E B F C A第一步后序最后一个元素是AA就是整棵树的根。在中序里A左边是“D B E”右边是“F C”。第二步左子树的后序序列是“D E B”。B是左子树的根。B在中序里左边是D右边是E所以B的左孩子是D右孩子是E。第三步右子树的后序序列是“F C”。C是右子树的根。C在中序里左边是F右边为空所以C的左孩子是F右孩子为空。还原结果和前序中序那棵树完全一样。后序中序的难点在于你处理右子树时后序序列要从后往前找根很容易把层次搞混。我的建议是每次找到根之后先在草稿纸上用括号把中序序列的左右区间框出来再根据区间长度截取后序片段不要光在脑子里推。把树还原出来之后无右孩子结点数还是4。这个例子也说明一个问题前序后序的组合不能唯一确定二叉树所以真题里如果给的是前序后序一般不会问“无右孩子结点有几个”只要给的是含中序的组合还原树并计数就是标准路径。4. 快速公式与边界条件为什么偶数和奇数结果不一样4.1 无右孩子结点数量的通式先给一般公式。对于任意二叉树无右孩子结点数 叶子结点数 只有左孩子没有右孩子的一度结点数。这个公式不针对某一道题而是所有“无右孩子”问题的基础。如果题目只说“这是一棵二叉树有 n 个结点”那么无右孩子结点数不能唯一确定。因为只靠 n你无法区分那些一度结点到底是有左无右还是有右无左。举例来说n 2 时如果根只有左孩子那么叶子1个、根也无右孩子总数是2如果根只有右孩子那么叶子1个、根有右孩子总数只有1。同样 n 2结果不一样。所以这类题必须有额外条件。4.2 完全二叉树中偶数和奇数的边界差异当题目指定为完全二叉树时情况就会收敛得非常清楚。完全二叉树的一个重要特征是除了最后一个非叶子结点其他非叶子结点如果存在都是左右双全。最后一层的结点全部靠左排列才可能导致一个特殊结点存在。设 n 为总结点数最后一个非叶子结点的编号是 ⌊n/2⌋。如果 n 是奇数那么2 × ⌊n/2⌋ 1 n也就是说最后一个非叶子结点的右孩子编号正好等于 n它是有右孩子的。既然它有右孩子整棵树就不存在“有左无右”的结点。此时无右孩子结点数 叶子结点数 n - ⌊n/2⌋ ⌈n/2⌉如果 n 是偶数那么2 × ⌊n/2⌋ 1 n 1这个值大于 n说明编号 n/2 的结点只有左孩子 n没有右孩子 n 1。于是这棵树里存在且只存在一个“有左无右”的结点编号是 n/2。此时无右孩子结点数 叶子结点数 1 (n - n/2) 1 n/2 1把两种情况合并起来就是下面这张表总结点数 n无右孩子结点数说明奇数⌈n/2⌉不存在有左无右结点偶数n/2 1编号 n/2 的结点有左无右4.3 这个公式在考场上的简化使用考场上拿到完全二叉树题目我的处理顺序是三步。第一步看 n 的奇偶性。第二步计算 ⌈n/2⌉。第三步如果 n 是偶数答案在 ⌈n/2⌉ 基础上加1如果 n 是奇数答案就是 ⌈n/2⌉。以 n 2011 为例它是奇数⌈2011/2⌉ 1006答案就是1006。这个流程十几秒就能走完。但要注意这套快速公式只能用在完全二叉树上。如果题目变成“一棵普通二叉树有2011个结点其中有……”这样的问法就必须结合更多条件比如叶子数、一度结点分布或者遍历序列不能直接套。5. 考场上的判断顺序和易错点清单5.1 判断顺序做题时不要急着代公式先用30秒把题目类型定下来。我的判断顺序如下。第一步确认题目给的二叉树类型。完全二叉树、满二叉树、普通二叉树、线索二叉树这四种情况处理方式完全不一样。第二步如果是完全二叉树算出最后一个非叶子结点编号 ⌊n/2⌋再判断它有没有右孩子。第三步求出叶子结点数。叶子编号从 ⌊n/2⌋ 1 到 n个数是 n - ⌊n/2⌋。第四步检查有没有有左无右的结点。只有 n 为偶数时才可能存在而且那个结点编号是 n/2。第五步把第三步和第四步的结果相加。第六步重新读一遍题干确认问的是“无右孩子结点”而不是“叶子结点”或者“无左孩子结点”。这三个问题答案可能不同。5.2 易错点结合长期做题的经验我总结出下面几个高频错误。第一把“无右孩子”和“叶子结点”混为一谈。叶子结点一定是无右孩子结点但无右孩子结点不一定是叶子结点。有左无右的非叶子结点在各类遍历题和带边界条件的树里都会出现。第二对完全二叉树只算叶子忘了检查 n 的奇偶性。n 是偶数时一定存在一个有左无右的结点这个结点不是叶子必须额外加进去。第三把完全二叉树当满二叉树处理。满二叉树要求每层都满完全二叉树只要求最后一层靠左连续。2011个结点连满二叉树应有的 2^k - 1 这个条件都满足不了不能用满二叉树公式去推。第四计算叶子结点数时用 n/2 而不是 ⌈n/2⌉。对 n 2011 来说n/2 等于1005.5四舍五入后是1006结果碰巧对但一旦 n 为偶数这种粗略处理就会出错。公式应该记成 n - ⌊n/2⌋ 或 ⌈n/2⌉。第五还原普通二叉树时只看遍历序列里的根不标注左右子树区间导致递归层次混乱。尤其是后序中序这种组合从后往前找根时很容易看串。5.3 检查方法算完答案之后可以用一组关系做完整性检查。对一棵二叉树设总结点数为 n有右孩子结点数 无右孩子结点数 n其中有右孩子结点数等于每个有右孩子的结点都数一次。在完全二叉树中如果 n 是奇数从编号1到 ⌊n/2⌋ 的所有结点都有右孩子所以有右孩子结点数是 ⌊n/2⌋。无右孩子结点数就是 n - ⌊n/2⌋。n 2011 时有右孩子结点数1005无右孩子结点数1006加起来正好等于2011。也可以用抽样验证先拿 n 5、n 6 这种小规模完全二叉树手算一遍如果总结出来的计数规律和小规模结果一致再代入大数。这个方法最适合考场紧张状态下的自查。最后再提醒一次考场上写完答案前把题干最后几个字重新读一遍。很多时候不是不会算而是把“无右孩子”看成了“无左孩子”或者把“无右孩子结点个数”看成了“叶子结点个数”。6. 同类题怎么练围绕“无右孩子”的扩展考点6.1 线索二叉树中的“无右孩子指针”“无右孩子结点”这个考点在408里还会和线索二叉树结合。中序线索二叉树中如果一个结点没有左孩子左指针指向前驱结点如果一个结点没有右孩子右指针指向后继结点。所以无右孩子结点的右指针会被线索化为中序后继。换句话说你看到的“右指针”不再是孩子而是一条线索。题目如果问“有多少右指针被线索化”本质上还是在问无右孩子结点的个数。复习线索二叉树时关键要区分两种指针状态正常右孩子指针和线索化右指针。判断标准就是看这个结点有没有右孩子。这和2011年第6题里用的是同一条判断逻辑。6.2 完全二叉树相关的其他公式既然2011年第6题把完全二叉树当作载体复习时可以顺手把下面这些结论一起掌握。这些结论彼此连通不要孤立记。叶子结点数n0 n - ⌊n/2⌋度为1的结点数n 为奇数时n1 0。 n 为偶数时n1 1此时 n/2 号结点只有左孩子。度为2的结点数n 为奇数时n2 (n - 1) / 2。 n 为偶数时n2 n / 2 - 1。树的高度对于含 n 个结点的完全二叉树高度 h ⌈log2(n 1)⌉。这些公式之间是连通的。用的时候可以结合一棵 n 6 的小树来验证不要死记。6.3 推荐复习路径如果你现在才开始集中突破“树”这一章建议按下面顺序来。第一先把二叉树的度、边数、结点数关系推明白。重点是 n0 n2 1 的来源以及 n n0 n1 n2 这个恒等式。第二把完全二叉树的编号规则和几个公式推导一遍。用 n 5 到 n 8 几棵小树手动画一遍比自己看十遍书都有效。第三把前序中序、后序中序还原树的方法练熟。408真题里给出中序序列的题目最终多半要落到重建树或判断某个结点位置这一步。第四遇到“无右孩子”“无左孩子”“叶子结点”“度为零的结点”这类字眼时先在草稿纸上写出各自的集合再看它们的交集和并集关系。刷题时养成这个习惯判断起来会快很多。最后提一个复习建议像2011年第6题这种题不要只记答案1006也不要把公式背下来就完事。真正考场上有用的是那套判断流程——先确认树型再算叶子再查有左无右最后相加。踩过一次坑之后就会发现这类题不是考计算是考你有没有把二叉树的结构真正理解透彻。
