今天聊聊代码训练营第15天的四道二叉树题目110平衡二叉树、257二叉树的所有路径、404左叶子之和、222完全二叉树的节点个数。如果你正刷到这里大概率已经熬过了二叉树前中后序递归遍历的坎处于“看题解秒懂、自己写就卡壳”的阶段。这四道题恰好卡在这个最难受的位置——它们全都要靠递归解决但每一道都在逼你换一种角度理解递归的返回值、终止条件和回溯路径。这篇文章不打算按题号平铺直叙地念一遍题解我想换个方式把这四道题当成一个整体来讲它们之间存在什么样的递进关系、每一道题真正在考什么、我在写这些代码时踩过哪些坑、又是怎么从“运行时错误”里一步步定位到问题所在的。看完之后你再去刷题思路会清楚很多。1. 四道题放在一起的奥妙——先看整体设计1.1 这四道题到底在考什么很多人刷题喜欢按题号一道一道刷刷完就忘因为没看出题目之间的内在联系。代码训练营把这一天设计成“二叉树专项日”其实是刻意为之的110、257、404、222这四道题看似互不相干实际上覆盖了二叉树递归的四种经典用法110平衡二叉树递归的过程中需要“返回高度”并“同时判断是否平衡”属于带状态传递的后序遍历。257二叉树的所有路径递归的过程中需要“记录走过的节点”并“在回溯时撤销选择”属于带路径收集的前序遍历。404左叶子之和递归的过程中需要在“父节点”这一层判断“左孩子是不是叶子”属于信息提前判断的遍历。222完全二叉树的节点个数递归的过程中需要“利用满二叉树性质做剪枝”属于利用结构特征的优化遍历。你看四道题全都在遍历但每一道题的“递归函数该返回什么”“在哪一层做判断”“需不需要回溯”都不一样。这正是递归应用的精髓不是你会写模板而是你能根据题目需求调整模板。1.2 为什么用递归作为主线二叉树的天然结构决定了递归是它的“母语”。一棵树的左右子树仍然是树这种自相似性让递归函数的逻辑几乎和数学定义一一对应。你写平衡二叉树的时候递归函数求的是“当前节点的高度”这个定义本身就是递归的当前节点的高度 max(左子树高度, 右子树高度) 1。你写二叉树的所有路径的时候递归函数求的是“从当前节点出发的所有路径”这个定义也是递归的。非递归写法能用栈模拟但代码复杂度和思维负担远高于递归。训练营把这个阶段的题目全押在递归上目的就是让你把递归彻底吃透。刷完这四道题之后你遇到二叉树相关的面试题就会形成肌肉记忆先想递归三要素——参数和返回值、终止条件、单层递归逻辑。1.3 四道题之间的递进关系这四道题不是随便凑在一起的我按自己的理解给你排一条学习线索第一层是110它教你在递归中“向上传递状态”。你不仅要算出子树高度还要把“是否平衡”这个额外的信息通过特殊返回值比如-1传递上去。第二层是257它教你在递归中“向下传递路径”。和110相反路径信息是自上而下积累的到了叶子节点才收获结果。第三层是404它教你在递归中“换视角判断条件”。判断的是左叶子但决策点在父节点——这是一个非常容易掉坑的思维转换。第四层是222它把递归和数学性质结合教你用完全二叉树的结构特征把O(n)优化到接近O(log n * log n)。一天刷完这四道等于把递归的“上传递、下传递、改判断、做剪枝”四种模式各练了一遍。以后再遇到递归题你至少能知道自己卡在哪一个维度。2. 两道“判断型”题目的核心拆解2.1 110. 平衡二叉树别用暴力法要学会自底向上平衡二叉树的定义很直白每个节点的左右子树高度差不超过1。这题最容易想到的解法是自顶向下写一个求高度的函数然后对每个节点判断左右子树高度差再递归判断左右子树是否平衡。思路没问题但你可能很快发现超时——因为每个节点都被重复计算了好几次高度。举个例子根节点求高度时要把整棵树遍历一遍然后递归判断左孩子时又把左子树遍历一遍再递归判断左孩子的左孩子时又遍历一遍。节点越多重复计算越严重整体复杂度退化到O(n²)。对一棵10万节点的树这个复杂度就是灾难。正确做法是自底向上把“判断平衡”和“计算高度”合并到一个递归函数里。后序遍历天然适合这个需求先递归处理左子树再递归处理右子树最后在中间节点汇总。你能拿到左右子树的高度一比较就知道当前节点平不平衡再把高度返回给上一层让上一层继续判断。这里的关键技巧是用一个特殊值来兼职“高度”和“是否平衡”两个信息。我见过不少同学的代码喜欢额外定义一个全局变量或pairint, bool也能工作但最精简的写法是用-1表示“这棵子树已经不平衡了”。如果左子树返回-1直接提前终止不用再看右子树如果右子树返回-1也提前终止。只有两个子树都正常才比较高度差并把真实高度返回上去。这个写法的另一个好处是能剪枝一旦某棵子树不平衡整棵大树注定不平衡没必要继续往下判断了。所以在递归函数里拿到左子树结果后先判一下是否为-1是就直接返回-1省掉右子树的递归调用。这在极端情况下能省不少时间。2.2 222. 完全二叉树的节点个数用满二叉树公式剪枝完全二叉树的定义是除了最后一层其他层都是满的且最后一层的节点都靠左排列。这题最朴素的做法就是普通遍历不管什么二叉树我递归数一下左右子树节点数再加1结果肯定对复杂度O(n)。这题这么出就没意思了完全二叉树的性质完全没用上面试官一定会追问“能不能更快”。那么完全二叉树有什么特殊之处呢一个关键结论是如果一棵子树是满二叉树那么它的节点总数可以直接用公式2^h - 1算出来不用一个个数。所以优化的思路就变成了在递归过程中尽可能多地用公式结算少做真正的递归遍历。具体做法是对当前节点分别沿着左孩子的左孩子一路走到最底计算左侧深度沿着右孩子的右孩子一路走到最底计算右侧深度。如果两侧深度相等说明这棵子树是满二叉树直接返回2^leftDepth - 1。如果两侧深度不等说明当前子树不是满二叉树那就老老实实递归处理左右子树再相加加1。你可能会担心这么搞不是还是要遍历很多节点吗实际上完全二叉树的递归路径非常短。每一次“两侧深度不等”的分支都会让问题规模减半左右复杂度稳定在O(log n * log n)级别也就是高度乘上每次判断高度的代价。实测下来这个版本比普通遍历快一个数量级。这里有一个实现细节容易出错有些文章写公式是(2 leftDepth) - 1这个写法其实是2的leftDepth1次方减1要求leftDepth是从0开始计数。如果你用的是“从根节点到最左叶子经过的边数”来定义深度那么公式应该是(1 leftDepth 1) - 1。我习惯写一个完整版先算出leftDepth和rightDepth指的是“从当前节点出发沿着单侧走到叶子经过的节点数减一”然后if相等返回(2 leftDepth) - 1这个2 leftDepth等价于2^(leftDepth1)。2.3 两道判断题的共同心法做完这两道题你有没有发现一个共同点它们都是在递归的过程中利用“返回值的特殊性”来减少计算量。110把高度和平衡状态合并用-1做哨兵222把“是不是满二叉树”的判断融进高度计算相等就直接用公式结算。它们都不是老老实实遍历完整棵树才得出结论的而是利用结构性质提前结束。这个思维方式对后续很多题目都有帮助比如判断对称二叉树、求二叉树直径等都是同一个套路在递归返回值上做文章。另外这两道题都在提醒你做题前先看一眼题目给了什么特殊性质。完全二叉树这个条件如果换成普通二叉树222题的优化方案就完全不成立。这就是为什么面试官喜欢拿这题考你——看你能不能识别并利用题目给出的结构特征。3. 两道“收集型”题目的实操要点3.1 257. 二叉树的所有路径回溯让每次选择被记住二叉树的所有路径这题题目要求返回所有从根节点到叶子节点的路径格式是“1-2-5”这样的字符串。一听“所有路径”就知道这题肯定和前序遍历脱不了干系你必须先往左走到底记录沿途节点再退回来往右走再记录这样才能把每条路都走一遍。这里最容易写崩的地方在于“退回来”这个动作。很多初学者第一次写这题会写出一个看起来没毛病的递归——把当前节点加进路径递归左子树再递归右子树——但结果发现路径串成了一长条左子树的路径和右子树的路径混在一起完全不是预期的样子。问题出在哪呢因为你的路径列表是共享的。第一次递归走完左子树的最深路径后列表里还残留着那些节点如果不清理下一次递归右子树时列表里就会带着左子树的节点。这个“清理”操作就叫回溯在代码里具体体现为递归调用之后的pop_back()。我给的写法是用一个vector path来记录路径每次递归返回后进行回溯。有个细节值得说一下收获结果的地方不是递归函数的开头而是叶子节点。判断条件就是当前节点的左孩子和右孩子都为空。到了这个位置把path转换成字符串加入result数组。你可能会问为什么不在进入递归时就收获因为路径要到叶子节点才算完整半路的节点只能算是“途径”不能算结果。字符串拼接也是这题的一个小考点。不能用“-”把整个vector一次join因为C标准库没有现成接口。我的做法是遍历path前n-1个元素后面都加-最后一个元素只加数值。这个写法够直白也避免各种off-by-one错误。3.2 404. 左叶子之和陷阱在于“判断父节点”左叶子之和这题题目名字就暴露了考点什么是左叶子叶子节点是没有子节点的节点左叶子就是它是父亲节点的左孩子而且它自己又没有孩子。判断条件看起来很简单但真动手写代码时很多人第一个版本就写错了。常见的错误版本是这样递归遍历时如果当前节点是叶子节点就判断它是不是左孩子是就累加。听起来逻辑没问题实现起来却发现——你根本不知道当前节点是不是左孩子。递归函数从头到尾只拿到当前节点和它的孩子拿不到“我是谁的孩子”这个信息除非你给递归函数额外传一个bool参数。更简洁的解法是把判断放在父节点当前节点的左孩子不为空且左孩子的左右子树都为空那么这个左孩子就是左叶子累加它的值。这个思路一出来代码就非常清爽了不需要额外传参不需要判断当前节点是左是右只需要在遍历到每个父节点的时候多看一眼它的左孩子。这题的另一个坑是漏判。有些同学用层序遍历做遍历到某个节点时只检查它自己是不是左叶子结果发现根节点的左叶子永远统计不到因为根节点没有父节点。用父节点判断法就能完美规避这个问题因为我们在递归左子树和右子树的过程中每个节点都会充当一次“父节点”的角色。写完这题你会重新理解一句话递归不是在处理“当前节点是谁”而是在处理“当前节点能对自己知道的信息做什么”。左叶子这个信息只在父节点这一层是显式的换到子节点视角就变成隐式了。这就是思维转换的核心。3.3 为什么路径题必须用前序遍历257题我强调用前序遍历中-左-右404题则前中后序任意遍历都可以这两者之间的区别值得展开说说。路径题必须前序的原因在于路径是从根节点开始的。你要记录从根到叶子的完整路线就必须先访问根把根节点加入路径再往左右走。如果用后序遍历等你拿到左子树的结果时根节点已经被处理过了路径根本拼不起来。左叶子之和这题则没有这个限制。左叶子的判断只依赖“父子关系”这一条局部信息遍历顺序不影响判断结果。前序可以中序可以后序也可以因为你在任何一个时机访问某个节点时都能同时看到它的左孩子。我把这个区别总结成一个原则如果题目关心“从根到当前节点的路径”优先前序遍历如果题目只关心“某个节点自身或局部的属性”遍历顺序无所谓。这个原则对后续很多题目同样适用例如求二叉树的最大深度后序遍历最顺手求二叉树的前序遍历结果就必须前序。4. 完整代码实现与逐步解说4.1 110题的C实现与执行流程我先把题解的完整代码贴出来然后拆开细讲。class Solution { public: int getHeight(TreeNode* node) { if (node nullptr) return 0; int leftHeight getHeight(node-left); if (leftHeight -1) return -1; int rightHeight getHeight(node-right); if (rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return max(leftHeight, rightHeight) 1; } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } };先看终止条件node为空返回高度0。这是递归的基石空树高度就是0没什么好商量的。再看单层逻辑先求左子树高度如果左子树返回-1说明左子树内部已经不平衡了没必要再求右子树直接向上一层传递-1。这是一种剪枝能让代码在发现不平衡时尽早返回。右子树同理。然后比较左右子树高度差如果超过1说明当前节点也不平衡了返回-1。否则正常返回当前节点的高度。最后主函数只要判断根节点的高度是不是-1就行了。这个实现最巧妙的地方在于返回值的含义是“当前子树的高度”-1是一个绝对不可能出现的非法高度用它兼作错误信号不会和合法值冲突。如果你用debug模式跟着执行一遍会发现递归的顺序非常符合直觉先一路跑到左子树最深处拿到高度再逐层回退接着再进入右子树。对一棵平衡树整个过程会访问所有节点一次对一棵不平衡的树可能访问到一半就提前返回了。4.2 257题的C实现与回溯过程class Solution { public: void traversal(TreeNode* cur, vectorint path, vectorstring result) { path.push_back(cur-val); if (cur-left nullptr cur-right nullptr) { string sPath; for (int i 0; i path.size() - 1; i) { sPath to_string(path[i]); sPath -; } sPath to_string(path[path.size() - 1]); result.push_back(sPath); return; } if (cur-left) { traversal(cur-left, path, result); path.pop_back(); } if (cur-right) { traversal(cur-right, path, result); path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root nullptr) return result; traversal(root, path, result); return result; } };我故意选择先用vector 存路径最后统一转字符串而不是一边递归一边拼字符串。因为一边拼字符串时回溯不仅要从path里删除节点还得从字符串里删掉对应的“-”和数字非常容易出错。用vector暂时存数字逻辑清晰很多。进入递归后第一时间把当前节点值加入path这比在递归函数外面提前加入要稳妥。然后判断是否为叶子节点如果是就构造一条结果字符串保存后返回。这里有个细节值得注意叶子节点返回时没有对应的pop_back操作。为什么因为调用它的父节点在调用结束后会执行pop_back把父节点自己加入的那个孩子弹出。如果你在叶子节点里多写一次pop_back反而会把路径里其他节点的值弹掉导致上层路径错乱。这个点我在刚学的时候错了好几次。在父节点这边左孩子递归完成后立即执行path.pop_back()删掉的就是左孩子的值此时path恢复为“父节点及以上”的路径接着进入右孩子递归。这就是回溯的完整闭环。我强烈推荐你手动画一个只有三个节点的二叉树按递推顺序把path的内容写出来你会发现这个pop_back的位置和次数简直是精准咬合多一次少一次都会出问题。4.3 404题的C实现与判断逻辑class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; int sum 0; if (root-left ! nullptr root-left-left nullptr root-left-right nullptr) { sum root-left-val; } sum sumOfLeftLeaves(root-left); sum sumOfLeftLeaves(root-right); return sum; } };这个版本的代码看起来很短但信息密度很高。终止条件是根节点为空返回0。然后我们不做任何“当前节点是不是左叶子”的判断而是看当前节点的左孩子是不是一个左叶子。如果是就把它加到结果里。然后递归计算左子树和右子树的左叶子之和全部相加返回。你可能奇怪的是为什么递归调用sumOfLeftLeaves(root-right)时没有单独判断“右孩子是不是左叶子”因为右孩子天然不可能是左叶子右叶子属于它自己的问题会在它作为父节点时的递归逻辑里另行判断。如果右孩子也有自己的左孩子那个左孩子会在下一次递归中按正常条件被统计到。这个设计刚好避免了对“左右”身份的重复判断代码才得以这么精简。你也可以用前序遍历、中序遍历、后序遍历任意一种方式实现因为本体的遍历顺序对结果毫无影响。我手写的时候倾向于直接把递归写在返回语句里一行搞定左右子树的求和逻辑更紧凑。4.4 222题的C实现与满二叉树快速结算class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; TreeNode* leftNode root-left; TreeNode* rightNode root-right; int leftDepth 0; int rightDepth 0; while (leftNode) { leftNode leftNode-left; leftDepth; } while (rightNode) { rightNode rightNode-right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; } return countNodes(root-left) countNodes(root-right) 1; } };这段代码的核心思路是判断当前子树是否为满二叉树。判断方式很巧妙如果沿着左子树一路向左到达的深度和沿着右子树一路向右到达的深度相同那么这棵子树一定是满二叉树。为什么这个条件能成立因为完全二叉树的特性保证了如果左右两条边的深度一致则中间所有层都是满的叶子层也是满的。节点总数可以直接用公式结算。这里有一个值得注意的细节leftDepth和rightDepth的初始值都是0循环条件是节点存在。假设当前节点只有一个左孩子没有右孩子那么leftDepth会被算成多少如果左孩子没有左孩子leftDepth就是0rightDepth也是0深度相等公式返回2^1-1 1。但当前节点明明有两个节点。问题出在哪出在我上面代码的深度定义里leftDepth是“从当前节点的左孩子开始沿着最左路径走的边数”而不是“从当前节点开始算”。如果你采用这个代码版本leftDepthrightDepth的结论只适用于“左右子树的深度相等”此时以当前节点为根的子树确实是一个满二叉树。这个代码在LeetCode测试下是能通过的因为完全二叉树的结构本身保证了这种等深关系只在满二叉子树时成立。但如果你从0开始推可能会觉得困惑我建议你自己在纸上用一棵三层完全二叉树跑一遍这个代码把每个递归过程算一遍你会理解得更透。如果两侧深度不等说明当前子树不是满的直接递归计算左右子树的节点数再加1。这就是最终结果。这种递归写法与暴力遍历的区别在于遇到一棵以满二叉树为根的子树时不需要深入它的每个节点一次公式计算就拿到结果省下的递归调用是指数级的。5. 常见运行错误与排查技巧5.1 “运行时错误”最常见的三个来源写二叉树程序时为什么总是报运行时错误我梳理了一下自己做题和辅导别人的经验绝大多数情况逃不出这三个原因第一个是空指针解引用。这是二叉树题里最高的错误来源。很多同学写递归时默认当前节点一定有左孩子或者默认左孩子一定有右孩子结果在某个边界节点上直接崩溃。比如判断左叶子时你写了root-left-left如果root-left本身为空这里就直接运行时报错。这就是为什么我在404题强调先判root-left ! nullptr再判它的左右孩子。第二个是忘记处理空树。主函数入口第一行就应该检查root是不是nullptr。有的题不检查也能过测试那是因为测试用例恰好没有空树但只要给你一个空树整个递归直接崩。养成习惯二叉树题目拿到手先写if (root nullptr)的判断。第三个是递归没有终止条件。这个错误比较隐蔽因为你的递归函数看起来有返回但可能忘了在递归调用之前判断子节点是否存在导致递归沿着nullptr一直深入下去直到栈溢出。栈溢出的表现通常是“运行时错误”而非“答案错误”因为你的程序根本没正常返回。排查的时候优先检查递归函数的第一行和所有递归调用的前置条件。5.2 手写递归时的“防呆检查清单”我在刷二叉树相关的题目时总结了一条自查路线写代码之前在心里过一遍能拦住至少八成的低级错误第一写清楚递归函数的参数和返回值。返回值是一个数、一个布尔还是一个数组如果返回值同时承担多种信息用什么特殊值区分比如110题的高度和-1。第二终止条件写对。什么是这个递归的最小子问题通常是节点为空但是不是所有情况都是空节点终止比如257题的收获结果实际上是在叶子节点终止而不是在空节点。第三单层递归逻辑写出来之后问自己一句这层逻辑是否只处理了当前节点而没有越权去处理下一层的递归结果如果发现你手动访问了root-left-right这种层级大概率逻辑放错了位置。第四回溯与路径收集的对称性。有push_back就有对应的pop_back有递归调用就有对应的返回。如果不确定回溯放在哪个位置就画一条从根到叶子的递归路径手动模拟一遍。第五检查你的返回值是否能正确传递。后序遍历返回给父节点的值必须是当前子树处理完的最终结果不能有中间态残留。我在刷题时把这些条目用一句话记住参数定身份终止定边界逻辑定行为回溯定闭环。5.3 调试二叉树程序的实用技巧二叉树程序不好调试传统的加打印语句方式很痛苦因为树形结构不好在控制台里直观呈现。我分享三个实测有效的技巧第一个是“最小用例法”。不要直接拿大测试用例调自己构造一个人为的、结构最简单、但又覆盖目标逻辑的二叉树比如只有三个节点的树根节点1左孩子2右孩子3。这个用例可以测出大部分逻辑错误。如果三个节点的树都跑不对说明你的判断逻辑或递归顺序本身有问题没必要往大用例上浪费时间。第二个是“打印调用栈模拟”。在递归函数开头加一行cout打印当前节点值和当前路径或高度然后跟着输出跑一遍。你看懂了递归的实际调用顺序基本就能定位问题。这个技巧特别适合排查回溯类错误——你能直观看到path在进入递归和返回时分别长了什么样子。第三个是“纸上画递归树”。这个听起来原始但对理解递归结构极其有效。把每次递归当作树上的一个节点画出递归的进入和返回顺序标出每一步之后path或sum的值。我把这个习惯坚持了几十题之后写二叉树递归几乎很少再出“忘记回溯”这类错误。另外一个实用小技巧如果你用的是C调试时可以在递归函数里打印this指针的值辅助确认访问的到底是哪个节点对象。不过刷题时多数人用在线IDE这个技巧主要适合本地编译器环境。6. 刷题节奏与个人体会6.1 一天四题怎么安排才合理如果这四道题对你都是新题我建议按照我前面讲的学习顺序来先110再257再404最后222。理由很简单110最锻炼你对递归返回值的理解是基础中的基础257让你掌握回溯的节奏404帮你建立视角转换222则是综合应用。如果你已经有基础只是来巩固的那可以直接按题号顺序刷重点放在对比这四题的递归差异上。我自己的习惯是刷完当天的四道题后会花15分钟把四份代码并列放在一起逐行对比。看110的高度返回和222的高度返回有什么不同、看257的pop_back和404的无回溯有什么不同。这种对比式复习比单纯背诵题解有效得多。6.2 从一道题到一类题二叉树的递归方法论刷完这四道题你应该试着建立一个属于自己的二叉树递归方法论。我的总结是三个问题我在递归里需要知道什么信息这个信息应该由返回值携带还是作为参数传入我需要在什么位置做决策答案基本能覆盖大部分二叉树题目。需要子树的信息就用后序遍历把信息返回给父节点需要根到当前节点的路径信息就用前序遍历配合参数传递和回溯需要在父节点判断子节点的属性就在单层递归逻辑中多做一次检查需要利用树的结构特性就先分析特性再去设计剪枝条件。这套方法论不仅能解这四道题还能延伸到二叉树的最大深度、最小深度、翻转二叉树、对称二叉树、二叉树的最近公共祖先等经典题目。刷题的核心不是记住某道题的解法而是把题目拆解成几个基本问题然后用自己熟悉的方法论去组装。6.3 最后再分享一个训练营期间的心得我在实操中体会最深的一点是不要因为“看懂了”就跳过写代码这一步。二叉树递归题尤其如此看题解觉得清楚上手写还是会在终止条件或回溯位置上栽跟头。我刻意练习的方式是看完题解后合上答案自己独立写一遍写错了就对照着改把错误原因记录下来。这个“错误本”后来成了我的面试复习宝典。如果你今天刷完这四道题建议花一点时间把每道题的递归调用过程用笔画一遍把高度返回、路径回溯、左叶子判断、满二叉树结算这四个关键动作用自己的话讲清楚。讲得清楚的说明真正掌握了。后面遇到更复杂的树形动态规划、二叉搜索树操作时今天的这些基本功会成为你最扎实的底色。