二叉树递归进阶：平衡判断、路径回溯与完全二叉树计数

1. 这一天练的是什么二叉树的“规整”与“计数”刷到训练营第15天大部分人在这个节点已经开始上手二叉树而且不是简单的遍历就完事而是开始处理各种“带条件的节点筛选”。力扣110、257、404、222这四道题放在一起其实思路非常统一都在考察“递归返回什么”这件事。110 判断一棵树是否平衡本质是让递归返回“左边高度 vs 右边高度”的比较结果257 要求拿到所有根到叶子的路径本质是在递归过程中维护一个路径容器404 求和所有左叶子本质是“节点类型判定 条件累加”222 统计完全二叉树的节点个数本质是把“满二叉树”的数学性质用在递归分治上。换句话说第15天不是让你死记四个解法而是让你建立一种感觉拿到一道二叉树题先问自己三个问题——递归出口是什么每一层递归要往上传什么上传的信息如何被父节点利用我刚开始刷二叉树时特别容易犯一个毛病拿到题就想着“我要用一个全局变量收集答案”。但到了 110 这种题你会发现全局变量根本不好使因为你要的不是一个最终数字而是“这棵树合不合格”的中间状态。这四道题集中练习正好把“返回值设计”这个基本功掰开揉碎了讲透了。像我这样自学的之前看任何递归都觉得神奇直到用“递归三要素”反复套了七八道题才慢慢敢说“哦递归无非就是确定返回值语义、确定结束条件、确定单层逻辑”。这一天的题目就是最好的练习场。2. 一道一道拆四种典型解法与选型逻辑2.1 力扣110高度差的“全局状态”处理110 这道题题目描述很简单给定一个二叉树判断它是否是高度平衡的二叉树。所谓高度平衡就是每个节点的左右子树高度差绝对值不超过 1。最容易想到的暴力做法是写一个 getHeight 函数然后在每个节点上分别算左子树高度和右子树高度判断差值。这个做法没问题但时间复杂度是 O(n²)因为每个节点都要往下递归一遍高度。我一开始就是这么写的提交也能过但一看题解才发现可以有更聪明的做法。更优的方案是“自底向上”在递归求高度的过程中顺便检查是否平衡。如果子树不平衡直接返回 -1 作为信号如果平衡返回真实高度。这样每个节点只需要访问一次时间复杂度 O(n)。这里的关键设计是返回值不再单纯是“高度”而是“高度或 -1 这个特殊标记”。我管这种写法叫“返回值带哨兵”。它避免了你写一个额外布尔变量去记录全局状态因为二叉树的递归天然是自底向上的父节点必须等子节点算完才能判断自己所以把状态放在返回值里最干净。实现时要注意的是-1 这个特殊值不能和真实高度混淆。判断条件要写成int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); if (leftHeight -1 || rightHeight -1) return -1; if (abs(leftHeight - rightHeight) 1) return -1; return max(leftHeight, rightHeight) 1;2.2 力扣257路径收集的“回溯感”257 要求返回所有从根节点到叶子节点的路径输出格式是字符串数组比如[1-2-5, 1-3]。这道题让我第一次意识到“递归与回溯”是绑定在一起的。如果你想在递归过程中维护一个路径那么在往下走之前把节点加进去往上返回时再把这个节点拿出来这就是回溯。我最初写的时候犯过一个特别典型的错把路径作为字符串直接拼接向下传。比如定义string path然后用path - to_string(root-val)往下传。这样写能过因为字符串是按值传的天然带有回溯效果。但我觉得这样不够“硬核”因为一旦遇到“你不仅要路径还要路径对应的某些累计值”这类衍生题字符串拼接的写法会非常受限。我倾向用容器记录路径节点顺序是把当前节点加入path容器判断当前节点是不是叶子左右都为空是的话把容器内容组装成字符串不是叶子就递归处理左右孩子递归回来之后把当前节点从path中弹出。弹出操作就是回溯的体现也是很多新手容易漏的一步。漏掉会怎样路径会越攒越长最后输出的路径全都是根到某个深节点的超长路径。这个 bug 特别隐蔽因为小树最多两三层的样例根本测不出来。还有一点细节拼接路径字符串时注意区分第一个节点不要出现-1这种开头。我是先拼第一个值再循环拼后续的-x。2.3 力扣404左叶子的判定陷阱404 的题目很直白计算所有左叶子之和。难点不在“求和”而在“什么算左叶子”。左叶子必须同时满足两个条件它是它父节点的左孩子它本身没有左孩子也没有右孩子。很多第一反应是在递归时判断root-left ! nullptr root-left-left nullptr root-left-right nullptr如果成立就把root-left-val加进去。这个方向是对的而且我建议就用这种“站在父节点角度看左孩子”的思路而不是尝试在递归参数里传一个布尔标记表示我是不是左孩子。为什么不用布尔标记因为那样需要额外参数而且空指针的处理会更绕。站在父节点视角代码直观逻辑清晰只需要判断一次就够int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum 0; if (root-left !root-left-left !root-left-right) { sum root-left-val; } sum sumOfLeftLeaves(root-left); sum sumOfLeftLeaves(root-right); return sum; }这个写法有个很容易被忽略的细节当root-left本身就是左叶子时我把它加进了 sum但是我在递归处理root-left时并不会重复加它因为root-left作为子树的根它的左右孩子都不存在函数直接返回 0。所以这题不会重复计算。还有一个小坑题目给的是空树时和为 0。我的递归出口if (!root) return 0;天然覆盖了这种情况。但如果你的终止条件只写了if (root nullptr) return 0;在只有一个根节点的树上根节点本身不算左叶子那也是 0两个写法都能处理。2.4 力扣222完全二叉树的位运算思维222 是这四道题里最需要“数学思维”的一道。题目是给一棵完全二叉树求节点个数。最简单的解法是一个 O(n) 的遍历任何遍历方式都能数出来。但题解里更妙的一版利用了完全二叉树的性质如果一棵子树是满二叉树那么它的节点数是2^height - 1对根节点先算左子树最左链深度leftDepth再算右子树最左链深度rightDepth。如果leftDepth rightDepth说明左子树是一棵满二叉树左子树节点数可以直接用公式算出来再加上根节点 1 个然后递归去算右子树节点数即可。如果leftDepth ! rightDepth则说明右子树是满二叉树右子树节点数用公式算递归去算左子树。这个递归的时间复杂度是 O(log² n)因为每一层递归都要走一次“求最左深度”的流程而递归深度最多是 log n每一步求深度也是 O(log n)。我第一次看到这个解法时最大的认知升级是二叉树不一定非要“全部遍历”你可以利用树的特殊结构跳过一部分完全没有必要访问的子树。这种“能批量算就算”的思路在后面处理很多数据结构问题时都很有用。3. 完整代码与时间复杂度对比3.1 C参考实现方便直接对照提交力扣110 平衡二叉树class Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } int getHeight(TreeNode* node) { if (!node) 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; } };力扣257 二叉树的所有路径class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (!root) return result; dfs(root, path, result); return result; } void dfs(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); if (!node-left !node-right) { string s; for (int i 0; i path.size(); i) { if (i ! 0) s -; s to_string(path[i]); } result.push_back(s); } else { if (node-left) dfs(node-left, path, result); if (node-right) dfs(node-right, path, result); } path.pop_back(); } };力扣404 左叶子之和class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (!root) return 0; int sum 0; if (root-left !root-left-left !root-left-right) { sum root-left-val; } return sum sumOfLeftLeaves(root-left) sumOfLeftLeaves(root-right); } };力扣222 完全二叉树的节点个数class Solution { public: int countNodes(TreeNode* root) { if (!root) return 0; int leftDepth 0, rightDepth 0; TreeNode* left root-left; TreeNode* right root-right; while (left) { leftDepth; left left-left; } while (right) { rightDepth; right right-left; } if (leftDepth rightDepth) { return (1 (leftDepth 1)) - 1 countNodes(root-right); } else { return (1 (rightDepth 1)) - 1 countNodes(root-left); } } };这里解释一下 222 代码里的公式如果左子树深度等于右子树深度则左子树是满二叉树且满二叉树高度为leftDepth 1从根到叶子层数节点数为2^(leftDepth1) - 1。这个数包含了左子树全部节点加上根节点 1 个再递归处理右子树。注意我没有给根节点单独加 1因为2^(h1) - 1已经包含了根节点本身。同理另一种情况算的是右子树是满时的节点数。3.2 复杂度与写法对比表题目遍历方向时间复杂度空间复杂度关键技巧110 平衡二叉树自底向上O(n)O(n) 递归栈返回值兼做标记257 二叉树路径前序O(n * L) L为路径平均长度O(n) 递归栈 路径容器回溯弹出404 左叶子之和任意序O(n)O(n) 递归栈父节点视角判定222 完全二叉树节点分治O(log² n)O(log n) 递归栈满二叉树公式剪枝看这张表就能发现第15天这组题基本覆盖了二叉树递归的几种常见“动作”比较、收集路径、条件累加、数学剪枝。这些动作组合起来就是你后面刷二叉树进阶题的基础招式。4. 这组题最容易踩的坑4.1 递归返回值与“全局哨兵”混用110 题里我用 -1 当特殊标记但有些同学会在返回值之外再维护一个全局的bool balance然后让递归函数返回高度。这样写也能AC但有一个隐患递归函数一旦变复杂你很容易忘记在某些分支更新全局变量导致返回值正常但全局状态被漏判。我的建议很简单能用返回值表达状态就不要用外部变量。原因有两个一是返回值是天然自带回溯效果的每个递归栈帧都有自己的返回路径互不干扰二是全局变量在并发或多次调用场景下要手动重置容易产生脏数据。4.2 路径题的重复追加与回溯遗漏257 题我见过太多人卡在了“结果路径重复”上。典型错误是把当前节点推进去后在处理完左孩子递归之后没有弹出导致右孩子递归时路径容器里多了一个节点。有个自查技巧在递归函数入口处打印一下当前容器里的路径再打印一下当前处理到的节点一眼就能看出容器元素是不是只增不减。如果发现容器长度超过了树高肯定是回溯没写好。另一个小坑是字符串拼接效率。如果每次递归都重新拼接一个字符串往下传时间复杂度会从 O(n) 恶化到 O(n²) 级别因为每个节点都要复制一份完整的路径字符串。虽然力扣上小数据量看不出差别但最好从一开始就用容器回溯的习惯遇到大数据也稳。4.3 求“左叶子”时的空指针判断顺序404 题最经典的报错是root-left-left访问了空指针。比如你在判断root-left是否存在后就觉得万事大吉但root-left的左右子树可能有一个是空的。所以正确的判断条件是root-left !root-left-left !root-left-right这里每一个条件缺一不可。省略!root-left-left会导致把“有右孩子但不是左叶子”的节点也算进去省略root-left会在空指针上直接段错误。我还见过一种写法是把判断逻辑放进递归到左孩子时判断“我是不是左孩子”需要额外传 parent 或 isLeft 参数。这种写法我强烈不建议。它会多一层判断而且你得小心在递归到根节点时是特殊情况。站在父节点判断是这道题代码量最少、最不容易错的方案。4.4 222 题的位运算优先级与边界值222 题的代码里(1 (leftDepth 1)) - 1很容易出错的地方是括号漏掉、优先级理解错误、或者当leftDepth 1接近 31 时左移溢出。题目给的数据范围一般不会走到那种极端但写代码时还是加上括号避免机器解析优先级和你预期不一致。另外有些同学在写递归时把“返回左子树节点数 右子树节点数 1”当成默认做法这没错但这完全没利用完全二叉树的性质复杂度是 O(n)。如果你是在面试中遇到这题建议两种解法都提一下先讲朴素遍历再抛优化思路这比只扔一个 O(n) 的做法更能体现你对数据结构的理解。5. 个人体会与下一步计划这四道题刷下来我最明显的感受是二叉树题目的“模型感”开始成型了。所谓模型感就是你看到一棵树不再只是看到一个对象结构而是能自动联想到“我要向子节点要什么、父节点怎么用”。以前我刷题喜欢追求“代码最短”后来发现这是假效率。真正的高效是“代码语义清晰”。比如 110 题的 -1 哨兵牺牲了一点“纯数学美感”但换来的是“任何人一看就懂这是非法状态”这才是有价值的写法。404 题也一样站在父节点判断左叶子少绕了一圈弯正确率肉眼可见地提高了。下一步我打算继续刷二叉树的“构造类”题目就是那种给你前序中序让你重建二叉树、或者给你序列化字符串还原树结构的题。因为第15天解决了“怎么遍历、怎么取数”的问题后面的构造题才会真正考验“怎么在递归中切片”。到那时今天养成的“返回值设计 回溯容器维护”这两个习惯会直接派上大用场。还有一个很实用的心得想分享给正在刷题的朋友遇到一组题不要只做完就翻篇。试着把每道题的解法抽象成一句话。比如这一轮我的四句话是用高度兼做平衡标记、用容器回溯拿路径、站在父节点判断左叶子、用满二叉树公式剪枝。等下次遇到新题你的大脑会自动检索这些“知识卡片”比重新推演一遍快得多。