刷二叉树刷到第十三天我最大的感受是递归函数的调用栈一深人就开始懵。不是不懂“递归”这两个字而是拿到一道题不知道递归函数该返回什么、该在哪一步做处理、什么时候该回溯。代码随想录训练营第十三天的这四道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数刚好把这些问题全部覆盖了一遍。四道题看起来是四个独立题目实际是一套组合拳高度和深度的概念、先序后序各自的应用场景、回溯在递归里的位置、以及完全二叉树的数学性质。我把这四道题放在一起复盘了一遍发现只要把几个关键点打通很多二叉树递归题都能顺手做出来。1. 先把“深度”和“高度”掰扯清楚后面四道题才做得下去这四道题里110题是直接考平衡二叉树的而平衡二叉树的定义依赖于“高度”。但很多人在这一步就被绕晕了因为深度和高度这两个概念长得太像网上的定义又各说各话。不把这个问题钉死后面全是糊涂账。1.1 深度是从根往下数的高度是从叶子往上数的我的个人建议是记住两句话就够了深度depth从根节点到当前节点经过的节点数或边数方向是自上而下。高度height从当前节点到最远叶子节点经过的节点数或边数方向是自下而上。拿一棵最简单的三层满二叉树来看1 / \ 2 3 / \ \ 4 5 6节点1的深度是1节点2和3的深度是2节点4、5、6的深度是3。反过来看高度节点4、5、6作为叶子节点高度是1节点2的高度是2整棵树的高度取决于根节点到最远叶子的距离也就是3。这里有个细节经常引起争论深度和高度到底是按节点数算还是按边数算。LeetCode里通常用节点数来定义也就是根节点深度为1、叶子节点高度为1。如果你在别的教材里看到根节点深度为0的写法那就是按边算了不影响算法思路但写代码时初始值要对齐。1.2 求深度用先序求高度用后序——这不是风格偏好是遍历顺序决定的我见过很多人一上来就问“求个深度而已用哪种遍历不一样吗”还真不一样。求深度是从根节点开始往下探每走一层就把层数加一这是典型的先序遍历场景先处理当前节点再去递归孩子。求高度是先知道左右子树各自的高度再取最大值加一得到当前节点的高度这是典型的后序遍历场景先递归到底层再把结果一层层往上返。我在训练营里学到的一个口诀是“先序往下带参数后序往上返结果”。求深度时你往往需要一个参数记录当前层数每层递归自己往下传求高度时你不需要额外参数递归函数的返回值本身就代表子树高度。这套区分在110题里会直接体现出来。如果题目要求判断一棵树是否平衡你要算的是每个节点的左右子树高度差那天然就是后序遍历。很多人在110题里卡住根本原因不是不会写递归而是没有意识到这个题本质上是在“从下往上收集高度信息”。2. 110.平衡二叉树后序遍历求高度剪枝才是灵魂平衡二叉树的定义本身不难理解一棵树是平衡的当且仅当每个节点的左右子树高度差的绝对值不超过1。注意是“每个节点”不是只看根节点。这个限定条件让很多人第一次提交的时候挂掉——只比较了根节点的左右子树高度没有递归往下检查。2.1 题目到底在考什么先把题目要求翻译成人话给定一棵二叉树判断它是不是高度平衡的。这里的“高度平衡”就是上面说的每个节点都满足左右子树高度差不超过1。暴力做法很容易想到写一个求高度的函数然后在每个节点上调用这个函数比较左右子树高度差再递归检查左右子树。这样确实能过但问题在于重复计算严重——求上层节点高度时把下层节点遍历了一遍求下层节点高度时又遍历了一遍时间复杂度是O(n log n)级别的最坏情况下会退化到O(n^2)。正确的做法是把求高度和判断平衡合并到一次递归里用后序遍历一边算高度一边检查平衡性。2.2 为什么返回-1这个“哨兵值”后序遍历递归函数的核心设计是返回值代表当前节点的高度。但如果当前节点的左右子树已经不平衡了我们其实不需要再往上精确返回它的高度只需要告诉上层“这里已经坏了”。这时候一个常用技巧是返回-1作为哨兵值。代码我直接贴在下面这个版本我反复写了好几遍是目前最顺手的写法class Solution { public: int getHeight(TreeNode* node) { if (node NULL) 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 1 max(leftHeight, rightHeight); } bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } };这里有一个我一开始没想通的点为什么在递归返回-1之前要先检查leftHeight和rightHeight是否已经为-1其实这是提前终止。如果左子树已经不平衡了那当前节点和右子树的高度差已经没有继续判断的意义了直接往上抛-1避免无意义的递归。这个操作就是剪枝。2.3 代码落地与三个容易翻车的地方第一个坑忘了检查子树是否已经不平衡。很多第一版代码会写成这样int leftHeight getHeight(node-left); int rightHeight getHeight(node-right); if (abs(leftHeight - rightHeight) 1) return -1;表面上看逻辑没错但leftHeight是-1的时候abs(-1 - rightHeight)可能恰好小于等于1于是这个节点被误判成平衡。实际上左子树早就挂了返回值却被吞掉了。所以必须先判断子树返回的-1再去做高度差判断。第二个坑递归终止条件。空节点返回0这个基本不会错。但如果题目定义的叶子节点高度是0你需要相应调整终止条件的返回值。这里又回到第一节说的深度和高度按节点数算空节点高度为0叶子节点高度为1代码就是这么对应的。第三个坑只有根节点的树。很多人写isBalanced时习惯性判断root为空返回true但容易漏掉只有一个节点也应该返回true的情况。上面的解法其实已经天然覆盖了单节点树左右子树都为空高度差为0getHeight返回1不是-1所以返回true。时间复杂度的分析也值得记一下每个节点只被访问一次每次操作是常数时间的比较和绝对值运算整体O(n)。空间复杂度主要是递归调用栈的深度最坏情况退化成链表时是O(n)平均情况下是O(log n)。3. 257.二叉树的所有路径回溯不是玄学它是递归的“后悔药”如果110题让你理解了后序遍历“从下往上返回结果”那257题就是完全相反的思路从上往下记录路径走到叶子节点就把路径存起来然后掉头往回走。这个掉头的过程就是回溯。3.1 为什么这题必须用先序题目要求返回所有从根节点到叶子节点的路径比如1 / \ 2 3 \ 5输出是[1-2-5, 1-3]要拼出路径你必须先拿到根节点的值然后向左右子树扩展所以根节点要先被处理——这就是先序遍历。中序和后序在这种场景下都不合适因为等你处理到根节点的时候路径已经很难拼回去了。3.2 path.pop_back() 到底在做什么这是我第一次刷这题时最懵的地方。路径问题的常规写法是用一个vector path来记录当前走过的节点然后每次递归返回时要把path末尾的节点弹出去。为什么因为path是共享的你从子树A回来之后path还是之前的样子如果不把子树A的节点弹出进入子树B时路径就不对了。我用一个具体的例子演示这个过程。还是上面那棵树初始path为空根节点1入pathpath[1]。往左孩子2走path[1,2]接着往右孩子5走path[1,2,5]此时5是叶子把“1-2-5”加入结果。然后递归返回到节点2此时就要把5弹出path[1,2]。再返回到根节点1把2弹出path[1]。再往右孩子3走path[1,3]3是叶子加入“1-3”。如果少了pop_back这一步进入右子树3时path还是[1,2,5,3]结果完全错乱。代码是训练营里比较经典的一个版本class Solution { private: void traversal(TreeNode* cur, vectorint path, vectorstring result) { // 进来先push当前节点保证叶子节点也能被记录 path.push_back(cur-val); // 到达叶子节点拼接路径 if (cur-left NULL cur-right NULL) { 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(); // 回溯 } } public: vectorstring binaryTreePaths(TreeNode* root) { vectorint path; vectorstring result; if (root NULL) return result; traversal(root, path, result); return result; } };注意这里有个细节path.push_back(cur-val)放在了函数开头叶子节点返回时并没有在递归函数内部做pop_back而是在上层递归的调用处做pop_back。这是很多教程的常规写法只需要记住“谁调用递归谁负责弹出”就不会乱。如果你喜欢对称的写法也可以在叶子节点return之前把path中的当前节点弹出效果一样。我自己的习惯是统一采用“调用处弹出”因为这样不需要在多个return路径上都想着弹出容易漏。3.3 隐藏的坑与迭代法扩展第一个坑递归函数里path参数的类型。如果你定义成vector path值传递那每次递归都会拷贝一份path不用pop_back也不会出错但空间开销会变大。我用引用vector 回溯操作才有意义。第一次写的人经常在这里卡住——用了值传递pop_back之后发现path没变因为pop的是副本。第二个坑字符串拼接的耗时。每个叶子节点都要把整个path转成字符串如果树很大这个开销不小。LeetCode里一般规模下没问题但如果是面试场景可以改成从根到叶子传string而不是vector每层递归直接拼接“val-”这样避免了最后再遍历path数组。代际写法各有优劣vector方式的好处是调试方便。再给一个迭代版的思路。用栈模拟递归时栈里不能只存节点还要同时存这条路径对应的字符串。每次压栈时把当前的路径字符串一起压进去弹出时就能直接得到完整路径。这个思路在遇到N叉树的所有路径问题时特别管用因为不需要手动回溯路径信息永远跟着当前节点走。class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root NULL) return result; stackpairTreeNode*, string st; st.push({root, to_string(root-val)}); while (!st.empty()) { auto [node, path] st.top(); st.pop(); if (node-left NULL node-right NULL) { result.push_back(path); } if (node-right) { st.push({node-right, path - to_string(node-right-val)}); } if (node-left) { st.push({node-left, path - to_string(node-left-val)}); } } return result; } };注意压栈顺序因为栈是后进先出想让左子树先处理就后压左子树。这是我每次写迭代法都会顺手检查一遍的地方顺序错了输出结果顺序会变虽然题目不一定要求顺序但调试时容易造成误导。4. 404.左叶子之和判断条件别写在叶子身上要去问它的父节点这道题的通过率在一开始刷的时候经常让人意外题目本身看起来很简单“计算给定二叉树所有左叶子之和”。但很多人第一次提交都在一个地方栽了跟头——把“左叶子”理解成了“左子树的所有叶子节点”或者“靠左边的叶子节点”然后开始各种排列组合判断。4.1 左叶子的定义坑先明确定义一个节点是左叶子需要同时满足两个条件它是叶子节点左右孩子都为空它是父节点的左孩子。注意第二条这个条件意味着判断左叶子这件事不能只看节点自己还要知道它的父节点。你在递归遍历的过程中遇到一个叶子节点你是不知道它是左孩子还是右孩子的除非把方向信息传下去或者换个角度——在父节点那里判断。我一开始就是这么踩坑的写一个递归函数遍历所有节点在叶子节点时判断它是不是左边来的结果不得不给递归函数添加一个isLeft参数。这个方案也能做但代码不够干净。更好的思路是在父节点那里判断“我的左孩子是不是左叶子”。4.2 从父节点判断的递归写法核心逻辑只有一段class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root NULL) return 0; int midValue 0; if (root-left ! NULL root-left-left NULL root-left-right NULL) { midValue root-left-val; } int leftValue sumOfLeftLeaves(root-left); int rightValue sumOfLeftLeaves(root-right); return midValue leftValue rightValue; } };解释一下midValue表示当前节点如果存在左叶子就把这个左叶子的值加进来。例如节点3的左孩子是叶子midValue就是叶子节点的值。然后分别递归左子树和右子树在子树里继续找左叶子。这里有个容易担心的点根节点为空的处理。空节点没有左孩子递归下去返回0自然就排除了。另一个容易担心的点是如果root-left本身就是一个左叶子那递归root-left时会不会把它再算一遍不会。因为递归root-left时那个叶子的左右孩子都是空midValue是0leftValue和rightValue也都是0所以它本身不会被重复计入。左叶子的值只在它的父节点那一层被计数一次。4.3 我用过的错误写法对比再分享一个反面教材。一开始我写过下面这个版本int sum 0; void dfs(TreeNode* node, bool isLeft) { if (node NULL) return; if (node-left NULL node-right NULL isLeft) { sum node-val; } dfs(node-left, true); dfs(node-right, false); }这个方案也能得出正确答案但问题在于需要维护一个额外的全局变量sum在多线程测试或多次调用时容易出问题需要给dfs增加isLeft参数理解成本比父节点判断法高如果题目要求返回int而不是用类成员变量写法要再调整。所以我最终推荐的还是父节点判断法。它完美体现了“递归函数返回子问题的解然后合并”这种思路和110题、222题的递归框架保持一致。一套框架打通四道题比你每道题记一个特殊套路要省力得多。这道题还有迭代版本用栈模拟中序或先序遍历都可以。判断逻辑不变只要在遍历过程中继续用“父节点看左孩子是否为左叶子”这个套路class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root NULL) return 0; stackTreeNode* st; st.push(root); int result 0; while (!st.empty()) { TreeNode* node st.top(); st.pop(); if (node-left ! NULL node-left-left NULL node-left-right NULL) { result node-left-val; } if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return result; } };我建议新手至少把递归版写熟迭代法作为一个参考思路去理解。因为递归版更贴近问题本质在面试中口述思路也更顺。5. 222.完全二叉树的节点个数暴力解O(n)不算完利用性质优化到O(log n × log n)这道题最直接的解法太明显了以至于很多人都忽略了它背后对完全二叉树性质的考察。LeetCode的提交记录里递归一行流写法就能过但如果你只写暴力遍历那就失去了这道题的真正价值。5.1 最朴素的递归版本先给最直接的递归版任何一个遍历都行class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; return 1 countNodes(root-left) countNodes(root-right); } };这段代码的逻辑很清楚空节点返回0非空节点等于自身1个加上左子树节点数加上右子树节点数。时间复杂度O(n)因为每个节点都会被访问一次。也可以用层序遍历逐层累加或者先序、中序、后序任何一种遍历方式去数本质都是O(n)。在完全二叉树这个前提下其实我们可以做得更快。5.2 完全二叉树的“天赐”性质完全二叉树Complete Binary Tree的定义是除了最底层节点可能没填满外其余每层节点数都达到最大值并且最底层的节点集中在最左边若干个位置。这个定义带来两个关键推论如果一棵完全二叉树的左右子树深度相同那么这棵子树一定是一棵满二叉树满二叉树的节点数可以直接用公式计算节点数 2^深度 - 1这里的深度按层数/高度从1开始算。举个例子高度为3的满二叉树节点数就是2^3 - 1 7。这个性质非常有用因为满二叉树的节点数不需要递归去数一个公式就能算出来。所以优化的方向是每到一个节点判断以它为根的子树是不是满二叉树如果是直接套公式返回如果不是再递归去算左右子树。5.3 优化代码和时间复杂度推导判断一棵子树是不是满二叉树不需要真的数一遍所有节点。只要从当前节点出发沿着最左路径走到底的深度和沿着最右路径走到底的深度相等就说明底层节点是铺满的这棵子树是满二叉树。代码是这样class Solution { public: int countNodes(TreeNode* root) { if (root NULL) return 0; TreeNode* left root-left; TreeNode* right root-right; int leftDepth 0; int rightDepth 0; while (left) { left left-left; leftDepth; } while (right) { right right-right; rightDepth; } if (leftDepth rightDepth) { // 以root为根的树是满二叉树节点数为2^(深度1) - 1 return (2 leftDepth) - 1; } return 1 countNodes(root-left) countNodes(root-right); } };注意代码里(2 leftDepth) - 1这个表达式。当leftDepth0时说明以root为根的树只有一个节点结果是(20)-11正确当leftDepth1时说明这棵树除root外还有左右两层即总共3个节点结果是(21)-13正确当leftDepth2时结果是7也正确。它等价于2^(leftDepth1) - 1只是用位运算写出来更简洁。这里我不建议你为了炫技强行记这个表达式理解成满二叉树公式就行代码写(1 (leftDepth 1)) - 1也完全没问题。时间复杂度分析是这个优化的精髓。每一层递归都会做一次向左、向右“探底”的操作每次探底需要O(log n)时间。但注意递归的次数不是O(n)因为一旦遇到满二叉树子树会直接返回公式结果。完全二叉树的递归过程中每棵子树要么是满的要么继续向下递归而递归深度最多是O(log n)。所以总时间复杂度是O(log n × log n)比O(n)低了一个量级。我实测过这个版本在LeetCode上的运行时间相比简单递归确实有明显提升。数据量越大、树越深优势越明显。5.4 这个优化对普通二叉树为什么不成立有人可能会想这个优化这么好我拿它去算普通二叉树的行不行不行。关键在于完全二叉树保证了一条性质如果节点左右深度相同子树必然满。但普通二叉树没有这个保证。一个普通节点左子树一直往左走到3层右子树一直往右走也到3层这不代表这棵子树所有层的节点都是满的。中间可能缺了很多节点比如某个右孩子为空。这时候套用满二叉树公式就会算错。这也是为什么很多算法题会特意在题目里强调“完全二叉树”就是为了给你提供额外的数学结构让某些计算能够跳过枚举。如果你无视这个条件等于把这个信息扔掉了。面试时如果问到这里我一般还会多说一句这个思路的本质是二分——用满二叉树的性质快速判断一条路径上有没有缺口有缺口就继续二分没有缺口就直接结算。和二分查找的思想是一脉相承的。6. 四道题刷完我对递归的三点新体会训练营第十三天这四道题刷完之后我回看自己前几天的代码发现有几个很明显的进步。先把这四道题的定位再串一遍110题教你用后序返回值表达“从下往上”的聚合信息257题教你用先序路径加回溯表达“从上往下”的探索过程404题教你巧妙选择判断节点——左叶子的计数放在父节点完成222题教你利用完全二叉树的数学性质跳过重复计算。第一点体会是递归函数的返回值设计决定了题目的难度。110题的返回值是高度同时用-1表达异常257题不需要返回值因为结果通过引用参数收集404题返回值是左叶子之和222题返回值是节点个数。返回值到底应该是什么取决于你要从子问题里拿到什么信息。这比背模板重要得多。第二点体会是回溯的“弹栈”动作不是递归的附加品而是递归过程的一部分。每次递归调用像一次“前进”pop_back就是“后退”。很多题目如果只记得写traversal(cur-left)而忘了在返回后恢复状态就会得到错误结果。257题的path.pop_back()是这四道题里最直观的回溯示范搞懂了这道题后面刷回溯算法专题会轻松很多。第三点体会是边界条件和空指针检查永远值得多写一遍。110题要提前检查子树返回值是否为-1404题要同时判断三个节点222题要处理root为空。这些都不是“炫技”而是扎实的工程习惯。我前几次提交出错十有八九是空指针判断漏了一个条件。如果你也在刷这组题目我建议按110、257、404、222的顺序来。这个顺序刚好对应了“最基础的递归求高度到需要回溯的路径搜索到父节点判断思想再到利用结构性质的优化”难度和思维跨度是平滑上升的。每道题都值得至少写两遍第一遍看题解写第二遍关掉题解自己默写。4道题都默写通过之后你会发现二叉树相关的递归不仅不绕了还能开始主动去设计递归函数的参数和返回值了。