尧图网站开发 
代码随想录训练营刷到第13天二叉树模块终于开始动真格的了。今天的四道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数——没有引入任何新概念用到的全是前面几天反复练习过的递归模板和遍历顺序但每一道都在逼你想清楚同一件事在遍历一棵树的过程中你究竟要从子节点带回什么信息、又要把什么状态往下传。想明白这一点是你从会背模板走向会做题的分水岭。四道题单看都不算难但组合在一起刚好把二叉树题目里最常出现、也最容易翻车的四类考点全覆盖高度与深度的计算方向、回溯路径的维护方式、基于父节点做条件判断、利用特殊树的结构性质做复杂度优化。这篇文章我把自己刷完这一天的解题笔记、完整代码和踩坑记录全整理出来。不管你是跟着训练营一起刷的还是自己刷 LeetCode 到二叉树模块卡住了都可以直接参考其中的思路和实现。1. 四道题串起来看这一天到底在练什么1.1 从遍历模板到遍历的工程化应用前十二天的内容核心任务是把树的各种遍历方式练熟层序用队列前序中序后序用递归或栈模板背得滚瓜烂熟。但能把一棵树完整走一遍和能在遍历中解决实际问题是两码事。第13天的四道题恰好就是从前者过渡到后者的第一组题目。110.平衡二叉树要求你在遍历的过程中顺便算出每个节点左右子树的高度差并判断是否合法257.二叉树的所有路径要求你在遍历的过程中维护一条从根到当前节点的路径到叶子节点时把整条路径输出404.左叶子之和要求你在遍历时针对特定类型的节点做筛选和累加222.完全二叉树的节点个数则要求你在遍历的时候利用树的特殊结构去跳过一部分不需要访问的节点。这四种需求几乎覆盖了二叉树非模板题的所有提问方式算值的、收集路径的、按条件过滤的、利用结构剪枝的。所以这一天在训练营的课程表里位置很特殊——它是遍历模板和树形问题之间的桥梁。1.2 四道题的难度梯度与考察侧重点用一张表把这四道题放在一起看对比会更清楚题目考察核心推荐路线时间复杂度核心技巧110.平衡二叉树高度计算合法性校验后序递归O(n)-1哨兵提前终止257.二叉树的所有路径路径记录状态回溯前序递归最坏O(n²)路径字符串拼接引用传参显式pop_back404.左叶子之和父节点上的条件判断后序/迭代均可O(n)左叶子要在父节点判定222.完全二叉树的节点个数特殊结构性质剪枝后序递归公式O(log²n)满二叉树节点数公式从面试角度看110 几乎是树形 DP 的入门题大厂笔试和小公司面试都常见257 是回溯思想的经典载体尤其适合作为能不能把路径想清楚的筛选题404 属于细节题考察你有没有被左叶子这个名词带偏222 则是典型的数据结构性质题考察你能否从完全二叉树的定义里挖出优化空间。把这四道题的定位搞清楚之后我建议按上面表格的顺序刷。前面一道题用到的后序遍历思路在后面的题目里会反复出现按这个顺序练习知识是叠加的而不是零散的。2. 110.平衡二叉树用-1哨兵一次后序遍历判断到底2.1 高度和深度先搞明白不然后面全乱平衡二叉树的判定条件是对树中的任意节点它的左子树高度和右子树高度之差不能超过1。注意这里说的是任意节点不是只检查根节点。很多初学者会只检查根节点左右子树的高度差结果一棵局部不平衡的树被误判为平衡树。要正确处理任意节点就必须在递归的每一层都做校验。而核心概念有两个高度height和深度depth。深度是从根出发往下数的根节点的深度是0越往下越大高度是从叶子出发往上数的空节点高度是0叶子节点高度是1越往上越大。在代码层面求深度适合前序自上而下传递求高度必须后序自下而上汇总。为什么因为高度需要先知道子树的情况才能算出来当前节点的高度等于 max(左子树高度, 右子树高度) 1。这是一个从子节点结果推导自身的过程天然就是后序。平衡二叉树这题问的是高度差所以正确的递归骨架必须是后序先拿左右子树的高度再判断当前节点是否平衡最后把当前节点的高度返回给上一层。理解了这一点代码基本不会写歪。2.2 朴素写法为什么会退化到O(n²)先看一种很直觉的写法写一个 getHeight 函数计算高度再写一个 isBalanced 递归判断每个节点是否平衡。int getHeight(TreeNode* node) { if (node nullptr) return 0; return 1 max(getHeight(node-left), getHeight(node-right)); } bool isBalanced(TreeNode* root) { if (root nullptr) return true; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); if (abs(leftHeight - rightHeight) 1) return false; return isBalanced(root-left) isBalanced(root-right); }逻辑完全正确但有一个明显的性能缺陷isBalanced 在递归检查每个节点时每个节点又都会调用 getHeight 把整棵子树重新扫一遍。最坏情况下比如一棵链状的树每个节点的高度计算都要遍历剩余的所有节点总复杂度会退化到 O(n²)。LeetCode 这题的数据范围是节点数不超过 5000O(n²) 在极端的测试数据下确实可能超时。但更重要的是面试场景你给出这个版本面试官几乎一定会问能不能优化。优化方向不是换一种遍历方式而是把算高度和查平衡两个职责合并到一次后序遍历里。合并的关键就是用一个特殊返回值标记不平衡。2.3 哨兵返回值一次遍历搞定计算和校验完整代码Cclass Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } private: 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; // 正常返回高度 } };每次递归先处理左子树再处理右子树最后处理当前节点——这是标准后序。返回值有两种含义正常时返回当前子树的高度异常时返回 -1。上层拿到 -1说明整个子树已经不满足平衡条件不用再往下判断了。为什么用 -1 而不是别的值因为高度永远是非负整数-1 在这个语义空间里是天然的安全哨兵。你可以在所有发现不平衡的路径上都返回 -1保证它不会和合法高度冲突也不用额外开一个全局变量去记录状态。这套正常返回值 哨兵异常值的写法在后面很多树形 DP 题里都会用到。比如计算二叉树直径、判断对称二叉树、求最近公共祖先时都可能需要一个特殊返回值来表示这条路走不通。提前在平衡二叉树这题把模式练熟后面会省很多力。Java 和 Python 的翻译也很直接Java 用 int -1Python 里同样用 -1 作为哨兵唯一要注意的是把 abs 和 max 换成对应语言的内置函数。逻辑完全一致换成你熟悉的语言写一遍理解会更扎实。3. 257.二叉树的所有路径回溯模板就藏在这道题里3.1 路径问题的核心谁在记录我从哪来110 练的是从子节点汇总信息到了 257 这里方向完全反过来了要把信息从根一路传到叶子。题目要求输出所有根到叶子的路径格式如 1-2-5。树的路径问题在思维上可以拆成两部分路径怎么生长以及路径在哪里结算。路径是从根开始生长的每递归进入一个节点这个节点的值就要被追加到当前路径的末尾。所以路径的生长方向与前序遍历天然匹配先处理当前节点再把路径往下传。这也是为什么树路径问题几乎都用前序而不是后序。但有一个细节很容易忽略递归返回到上一层时当前节点已经从逻辑上离开了这条路径它的值不应该再出现在路径里。这就是回溯的核心——状态要随着递归的进入而追加随着递归的返回而撤销。如果你不在返回前把当前节点从路径里撤掉路径就会被污染左子树走过的节点会被残留在右子树的路径里输出的路径就会多出一截谁都不认识的节点。3.2 标准回溯模板vector path 显式pop_back下面是我的写法也是代码随想录训练营里推荐的标准版class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root nullptr) return result; traversal(root, path, result); return result; } private: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); // 前序路径先记录当前节点 if (node-left nullptr node-right nullptr) { string s; for (int i 0; i path.size() - 1; i) { s to_string(path[i]) -; } s to_string(path[path.size() - 1]); result.push_back(s); return; // 叶子节点直接结算回到上一层再统一回溯 } if (node-left) { traversal(node-left, path, result); path.pop_back(); // 递归返回撤销左子树带来的状态 } if (node-right) { traversal(node-right, path, result); path.pop_back(); // 同理撤销右子树带来的状态 } } };解释一下为什么 pop_back 必须紧跟在递归调用后面。这里 path 是引用传递的整棵递归树共享同一个 vector。进入某个子节点前 push_back 一次递归返回后如果不清掉下一次进入兄弟节点时 path 里仍然留着上一个子树的值最终每条路径都会多出一截不属于自己的节点。另一个容易困惑的点叶子节点 push_back 之后没有立刻 pop_back谁负责清理答案是父节点。当 traversal(node-left) 返回时父节点那一层紧接着执行 path.pop_back()把叶子节点从 path 中弹掉。这个上层负责收回的约定是回溯递归里非常关键的设计——你把状态追加给别人你也要负责在返回后撤销。3.3 字符串传值的简化版省事但学不到回溯如果直接用 string 作为 path每次递归传值拷贝可以少写 pop_back代码短了很多class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; dfs(root, , result); return result; } void dfs(TreeNode* node, string path, vectorstring result) { if (node nullptr) return; path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); return; } path -; dfs(node-left, path, result); dfs(node-right, path, result); } };这版本的回溯是隐式的——每次递归创建新的 string返回后旧变量自动作废状态自然恢复。逻辑简洁可读性也好257 题的数据范围节点数最多100完全跑得动。但我依然建议在训练阶段先写引用回溯的版本。原因很简单后面的回溯算法章节才是重头戏。组合、排列、子集这些问题里路径的状态不能依赖字符串值拷贝解决必须用引用 pop_back 手动维护。树的路径问题是练习这套技能最好的场景因为树的结构天然给了明确的进入和返回时机。你在 257 上练熟了push_back 递归 pop_back的节奏后面写 permutations 时会顺手很多。而且面试官如果追问为什么用引用传 path你能讲出因为要显式回溯避免兄弟子树之间的状态污染这比只交一个值拷贝版本更能体现对递归原理的理解。4. 404.左叶子之和判定条件要写在父节点上4.1 站在叶子上看不清自己是谁练完汇总110和传递257两种方向第三道题加了一点刁钻的细节。左叶子之和的题意直白把所有满足左叶子条件的节点值加起来。但左叶子这个词藏了一个初学者最容易掉进去的陷阱。左叶子需要同时满足两个条件它是一个叶子节点也就是没有左孩子也没有右孩子它是某个节点的左孩子。问题在于当你站在一个叶子节点上你完全没有信息判断自己是左孩子还是右孩子。你自己的视角里只有我是不是叶子没有我在父节点的哪一边。方向是相对父节点才存在的所以判断逻辑必须上移到父节点那一层——检查当前节点是否存在一个左孩子并且那个左孩子本身是叶子。这个站在父节点看子节点身份的思路是这类题目和普通遍历最大的差别。很多人卡在 404 上不是不会遍历而是思维没有完成从节点本位到关系本位的切换。树的很多条件判断都是关系性的左叶子是父子关系右视图是层级关系最近公共祖先也是祖先-后代关系。尽早建立这个视角后面读树题会轻松很多。4.2 判定逻辑怎么写三种遍历次序都能做递归实现上我推荐后序版本因为结构最统一class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; int leftSum sumOfLeftLeaves(root-left); int rightSum sumOfLeftLeaves(root-right); int cur 0; if (root-left root-left-left nullptr root-left-right nullptr) { cur root-left-val; // 左孩子是叶子它就是当前子树能贡献的左叶子 } return leftSum rightSum cur; } };这个函数的语义是返回以 node 为根的子树中所有左叶子的和。递归的三段分别是左子树里有多少左叶子右子树里有多少左叶子当前节点自己能不能额外贡献一个左叶子也就是它的左孩子是不是左叶子。注意一个边界成立条件是root-left root-left-left nullptr root-left-right nullptr三个条件一个都不能少。少了 root-left空指针解引用直接崩少了后面任何一个非叶子的左孩子也会被误算进来。这个三条件判断就是整道题唯一的考点写对它就通过了。后序版本里函数本身要返回子树的累加结果用哪种遍历顺序最终结果都一样。你可以试试把返回挪到递归之前就是前序版本同样能 AC。真正重要的只有那个判定条件的位置和完整性。如果偏好迭代用栈模拟前序完全没问题判定条件一字不差class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; stackTreeNode* st; st.push(root); int sum 0; while (!st.empty()) { TreeNode* node st.top(); st.pop(); if (node-left node-left-left nullptr node-left-right nullptr) { sum node-left-val; } if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return sum; } };迭代版每次从栈里弹出一个节点马上检查它有没有左叶子孩子有就加上。栈的顺序不影响结果因为每条边都只会被它的父节点检视一次左叶子的判定天然和遍历顺序无关。5. 222.完全二叉树的节点个数别把特殊树当普通树刷5.1 完全二叉树的结构红利在哪到了第四题场景再次改变——不再强调遍历顺序而是强调结构认知。完全二叉树的定义很严格除最后一层外每一层的节点数都是满的最后一层的节点全部靠左排列。拿这个定义对比普通二叉树你会发现完全二叉树的形状被约束得非常死而这种约束正是优化的机会。最朴素的解法是暴力数递归遍历每个节点O(n)。n 如果只有几千这题明显能过——LeetCode 当前给的节点数上限是 5×10⁴暴力也不超时。但题目既然特意告诉你这是完全二叉树就说明出题人期望你利用它。关键观察是如果从某个节点出发沿着最左路径走到底的深度和沿着最右路径走到底的深度相等那么以这个节点为根的子树一定是一棵满二叉树——每一层都填满了。满二叉树的节点总数可以直接用公式层数为 h 时节点数等于 2^h - 1。这样一整棵满子树就不需要逐个节点去访问了。算法可以这样设计每到一个节点先量一量左右边界深度如果相等说明整棵子树是满的套公式直接返回如果不等说明当前子树没有填满继续往左右子树递归。递归到某个深度时遇到满子树就停住用公式收割结果。5.2 完整代码与复杂度推导class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; int leftDepth 0, rightDepth 0; TreeNode* leftNode root-left; TreeNode* rightNode root-right; while (leftNode) { // 沿着最左路径往下走数边数 leftNode leftNode-left; leftDepth; } while (rightNode) { // 沿着最右路径往下走数边数 rightNode rightNode-right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; // 等价于 2^(leftDepth1) - 1 } return 1 countNodes(root-left) countNodes(root-right); } };解释一下位运算。leftDepth 统计的是从当前节点的左孩子一路往左下走的边数。如果左右深度相等当前子树的层数是 leftDepth 1满二叉树的节点数就是 2^(leftDepth1) - 1。2 leftDepth就是把 2 左移 leftDepth 位相当于 2^(leftDepth1)所以(2 leftDepth) - 1就是这个公式的紧凑写法。如果不习惯位运算写成(1 (leftDepth 1)) - 1更直白。用一棵 6 个节点的完全二叉树走一遍流程根节点下有左子 L、右子 RL 有两个孩子 LL、LRR 有一个孩子 RL。在根节点左边界路径是 L→LLleftDepth 2右边界路径是 RRL 的右侧没有节点rightDepth 1。不相等不能套公式。递归左子树 L以 L 为根有 LL、LR 两个满孩子leftDepth 1rightDepth 1相等按公式直接返回 3 个节点2² - 1 3不用往下走了。递归右子树 R以 R 为根只有一个左孩子 RL没有右孩子leftDepth 1rightDepth 0不相等。继续递归到 RL左右深度都为 0返回 1R 的右孩子为 null返回 0。所以 R 子树总数为 1 1 0 2。整个树的总数 根自身的 1 左子树 3 右子树 2 6。这个例子很直接地展示了优化效果整棵左子树只量了两次深度就立刻出结果没有逐个节点访问右子树也算是最小规模的递归。真正的大数据量下这个剪枝能省掉大量无效遍历。复杂度分析每次进入节点都需要花 O(h) 的时间测量左右边界深度。对于一个完全二叉树递归到某个节点后左右子树中至少有一个是满的可以直接用公式返回因此需要继续递归的分支会迅速减少。总的递归深度是 O(log n)每个递归层级上的测量总耗时也不会超过 O(log n)所以整体的时间复杂度是 O(log²n)空间复杂度是递归栈的 O(log n)。5.3 暴力解虽然能过为什么还要学优化我知道很多人刷这道题时会有疑问LeetCode 上节点数上限是 5×10⁴直接写 count(root) count(root-left) count(root-right) 1 也能 AC为什么要费劲学这个满二叉树公式版本我从训练营和面试两个角度说下自己的理解。从训练营的角度这四道题是一个递进。前面几道题练的是如何把遍历用好222 练的是如何看出可以用数学跳步。如果你只满足于 AC 一个暴力解那这一天的最后一题就没有任何增量价值。真正值得吸收的是观察结构性质 → 把性质变成剪枝条件 → 用公式接管重复劳动这个思维链路。从面试的角度出了这题面试官真正想看的不是你数节点数数得快而是你会不会利用题面已经告诉你的完全二叉树这个性质。你在面试里如果主动说我可以先暴力 O(n) 保底然后再用满二叉树公式优化到 O(log²n)传递出来的信号是我不只会写模板我还会针对数据结构特性做复杂度分析。这种信号在很多场景下比 AC 本身更有价值。当然暴力解也有存在意义——它是你思路断掉时的兜底。我自己的习惯是先确保暴力解不出错再在暴力解的基础上加剪枝。这样即使优化部分写错了至少能保底拿分。6. 常见问题与排查技巧实录6.1 四道题最容易踩的坑一览我把实际刷题时收集到的坑整理成一个速查表每一个都是真实发生过的题目典型错误症状正确做法110混淆深度和高度用前序累计深度判断平衡高度走后序从子树结果推自身110每个节点重复算高度极端数据超时单次后序 -1 哨兵257忘记回溯左右子树路径互相污染递归返回后立即 pop_back257叶子节点仍继续递归空子树也被加入路径叶子节点直接结算路径并 return404判定条件少写右孩子检查左子树内部节点被当左叶子三个条件一个都不能少404站在叶子节点判断自己无法知道自己是不是左孩子把判断写到父节点222不利用满二叉树公式暴力遍历能过但无增量左右深度相等时直接套公式222位运算写错2 leftDepth 误写为 1 leftDepth换算成 2^(leftDepth1)-1 检查除了表里这些还有一个很隐蔽的细节110 的剪枝不完整。有人写了 -1 哨兵但在拿到 leftHeight 之后没有立刻检查而是继续调 rightHeight。这在语义上没错但浪费了一次递归。正确写法是拿到左子树结果先判断一次拿到右子树结果再判断一次见 -1 就立刻 return把剪枝效果做满。257 的字符串拼接也容易出格式问题。如果每一层都先把 - 拼在节点值后面最后一个叶子的值后面会多出一个 -。我常用的规避方法是像上面的代码那样到叶子统一拼接或者先收集到 vector 里到叶子再统一格式化。别在中间步骤贪图省事。222 的溢出问题也值得提一句。虽然当前数据范围不会触发但(2 leftDepth)在 leftDepth 较大时会超过 32 位 int 的上界。面试时可以主动提一句这里用 long long 更稳这是加分项。6.2 递归调试三板斧树的递归题我调试用的是三个土办法实测比纯看代码快很多。第一招打印递归轨迹。在函数入口打印节点值和当前递归深度在返回前打印返回值。可以用一个字符串把深度可视化void debug(TreeNode* node, int depth) { if (node nullptr) return; cout string(depth * 2, -) node-val endl; debug(node-left, depth 1); debug(node-right, depth 1); }这个缩进输出能直接看出递归的进入和返回顺序特别适合排查 257 这类路径问题——你能肉眼看到路径是在哪里被错误保留、在哪里被错误弹掉的。第二招准备一组最小的边界用例。树的题边界用例其实非常固定空树、只有一个节点的树、左斜树、右斜树、满二叉树、完全但不满的树。每道题刷完把这几个用例跑一遍基本能把隐藏 bug 全部暴露出来。比如 404 的判定用一棵三节点的树根 左叶 右叶就能立刻验证左叶子有没有被正确累加。第三招递归和迭代互验。同一道题分别写递归和迭代版本用随机生成的树跑对比。如果两个版本结果不一致通常问题出在遍历顺序或者状态恢复的时机上。这个办法对 257 尤其管用因为回溯阶段的时机错误很容易被版本间的差异暴露出来。提示刷树题最忌讳的是盯着代码空想。我一般建议先画一棵不超过四层的小树把递归的调用顺序在纸上推一遍再去和代码的打印结果对。纸上能推对代码基本就不会错。最后分享一点我自己的体会。刷完第13天这四道题我最大的变化不是记住了四个模板而是形成了一个新的思考习惯每个树题读完我会先问自己三个问题——当前节点要从子节点拿到什么信息当前节点自己要贡献什么信息这些信息该往上返回还是往下传给子节点110 要的是从子节点拿高度和合法性257 要的是把路径往下传给子节点404 是要从子节点拿求和结果、同时自己判断左叶子222 则是要从子节点拿节点数但同时利用满树公式跳过计算。一旦这三个问题想清楚代码怎么写几乎是水到渠成的事。这也是训练营这个阶段最值钱的东西——不是在练代码是在练建模。如果你也在这四道题上反复卡壳别急着看题解先把上面三个问题写在纸上想明白再动手效果会比背十遍题解都好。 
代码随想录训练营刷到第13天二叉树模块终于开始动真格的了。今天的四道题——110.平衡二叉树、257.二叉树的所有路径、404.左叶子之和、222.完全二叉树的节点个数——没有引入任何新概念用到的全是前面几天反复练习过的递归模板和遍历顺序但每一道都在逼你想清楚同一件事在遍历一棵树的过程中你究竟要从子节点带回什么信息、又要把什么状态往下传。想明白这一点是你从会背模板走向会做题的分水岭。四道题单看都不算难但组合在一起刚好把二叉树题目里最常出现、也最容易翻车的四类考点全覆盖高度与深度的计算方向、回溯路径的维护方式、基于父节点做条件判断、利用特殊树的结构性质做复杂度优化。这篇文章我把自己刷完这一天的解题笔记、完整代码和踩坑记录全整理出来。不管你是跟着训练营一起刷的还是自己刷 LeetCode 到二叉树模块卡住了都可以直接参考其中的思路和实现。1. 四道题串起来看这一天到底在练什么1.1 从遍历模板到遍历的工程化应用前十二天的内容核心任务是把树的各种遍历方式练熟层序用队列前序中序后序用递归或栈模板背得滚瓜烂熟。但能把一棵树完整走一遍和能在遍历中解决实际问题是两码事。第13天的四道题恰好就是从前者过渡到后者的第一组题目。110.平衡二叉树要求你在遍历的过程中顺便算出每个节点左右子树的高度差并判断是否合法257.二叉树的所有路径要求你在遍历的过程中维护一条从根到当前节点的路径到叶子节点时把整条路径输出404.左叶子之和要求你在遍历时针对特定类型的节点做筛选和累加222.完全二叉树的节点个数则要求你在遍历的时候利用树的特殊结构去跳过一部分不需要访问的节点。这四种需求几乎覆盖了二叉树非模板题的所有提问方式算值的、收集路径的、按条件过滤的、利用结构剪枝的。所以这一天在训练营的课程表里位置很特殊——它是遍历模板和树形问题之间的桥梁。1.2 四道题的难度梯度与考察侧重点用一张表把这四道题放在一起看对比会更清楚题目考察核心推荐路线时间复杂度核心技巧110.平衡二叉树高度计算合法性校验后序递归O(n)-1哨兵提前终止257.二叉树的所有路径路径记录状态回溯前序递归最坏O(n²)路径字符串拼接引用传参显式pop_back404.左叶子之和父节点上的条件判断后序/迭代均可O(n)左叶子要在父节点判定222.完全二叉树的节点个数特殊结构性质剪枝后序递归公式O(log²n)满二叉树节点数公式从面试角度看110 几乎是树形 DP 的入门题大厂笔试和小公司面试都常见257 是回溯思想的经典载体尤其适合作为能不能把路径想清楚的筛选题404 属于细节题考察你有没有被左叶子这个名词带偏222 则是典型的数据结构性质题考察你能否从完全二叉树的定义里挖出优化空间。把这四道题的定位搞清楚之后我建议按上面表格的顺序刷。前面一道题用到的后序遍历思路在后面的题目里会反复出现按这个顺序练习知识是叠加的而不是零散的。2. 110.平衡二叉树用-1哨兵一次后序遍历判断到底2.1 高度和深度先搞明白不然后面全乱平衡二叉树的判定条件是对树中的任意节点它的左子树高度和右子树高度之差不能超过1。注意这里说的是任意节点不是只检查根节点。很多初学者会只检查根节点左右子树的高度差结果一棵局部不平衡的树被误判为平衡树。要正确处理任意节点就必须在递归的每一层都做校验。而核心概念有两个高度height和深度depth。深度是从根出发往下数的根节点的深度是0越往下越大高度是从叶子出发往上数的空节点高度是0叶子节点高度是1越往上越大。在代码层面求深度适合前序自上而下传递求高度必须后序自下而上汇总。为什么因为高度需要先知道子树的情况才能算出来当前节点的高度等于 max(左子树高度, 右子树高度) 1。这是一个从子节点结果推导自身的过程天然就是后序。平衡二叉树这题问的是高度差所以正确的递归骨架必须是后序先拿左右子树的高度再判断当前节点是否平衡最后把当前节点的高度返回给上一层。理解了这一点代码基本不会写歪。2.2 朴素写法为什么会退化到O(n²)先看一种很直觉的写法写一个 getHeight 函数计算高度再写一个 isBalanced 递归判断每个节点是否平衡。int getHeight(TreeNode* node) { if (node nullptr) return 0; return 1 max(getHeight(node-left), getHeight(node-right)); } bool isBalanced(TreeNode* root) { if (root nullptr) return true; int leftHeight getHeight(root-left); int rightHeight getHeight(root-right); if (abs(leftHeight - rightHeight) 1) return false; return isBalanced(root-left) isBalanced(root-right); }逻辑完全正确但有一个明显的性能缺陷isBalanced 在递归检查每个节点时每个节点又都会调用 getHeight 把整棵子树重新扫一遍。最坏情况下比如一棵链状的树每个节点的高度计算都要遍历剩余的所有节点总复杂度会退化到 O(n²)。LeetCode 这题的数据范围是节点数不超过 5000O(n²) 在极端的测试数据下确实可能超时。但更重要的是面试场景你给出这个版本面试官几乎一定会问能不能优化。优化方向不是换一种遍历方式而是把算高度和查平衡两个职责合并到一次后序遍历里。合并的关键就是用一个特殊返回值标记不平衡。2.3 哨兵返回值一次遍历搞定计算和校验完整代码Cclass Solution { public: bool isBalanced(TreeNode* root) { return getHeight(root) ! -1; } private: 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; // 正常返回高度 } };每次递归先处理左子树再处理右子树最后处理当前节点——这是标准后序。返回值有两种含义正常时返回当前子树的高度异常时返回 -1。上层拿到 -1说明整个子树已经不满足平衡条件不用再往下判断了。为什么用 -1 而不是别的值因为高度永远是非负整数-1 在这个语义空间里是天然的安全哨兵。你可以在所有发现不平衡的路径上都返回 -1保证它不会和合法高度冲突也不用额外开一个全局变量去记录状态。这套正常返回值 哨兵异常值的写法在后面很多树形 DP 题里都会用到。比如计算二叉树直径、判断对称二叉树、求最近公共祖先时都可能需要一个特殊返回值来表示这条路走不通。提前在平衡二叉树这题把模式练熟后面会省很多力。Java 和 Python 的翻译也很直接Java 用 int -1Python 里同样用 -1 作为哨兵唯一要注意的是把 abs 和 max 换成对应语言的内置函数。逻辑完全一致换成你熟悉的语言写一遍理解会更扎实。3. 257.二叉树的所有路径回溯模板就藏在这道题里3.1 路径问题的核心谁在记录我从哪来110 练的是从子节点汇总信息到了 257 这里方向完全反过来了要把信息从根一路传到叶子。题目要求输出所有根到叶子的路径格式如 1-2-5。树的路径问题在思维上可以拆成两部分路径怎么生长以及路径在哪里结算。路径是从根开始生长的每递归进入一个节点这个节点的值就要被追加到当前路径的末尾。所以路径的生长方向与前序遍历天然匹配先处理当前节点再把路径往下传。这也是为什么树路径问题几乎都用前序而不是后序。但有一个细节很容易忽略递归返回到上一层时当前节点已经从逻辑上离开了这条路径它的值不应该再出现在路径里。这就是回溯的核心——状态要随着递归的进入而追加随着递归的返回而撤销。如果你不在返回前把当前节点从路径里撤掉路径就会被污染左子树走过的节点会被残留在右子树的路径里输出的路径就会多出一截谁都不认识的节点。3.2 标准回溯模板vector path 显式pop_back下面是我的写法也是代码随想录训练营里推荐的标准版class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; vectorint path; if (root nullptr) return result; traversal(root, path, result); return result; } private: void traversal(TreeNode* node, vectorint path, vectorstring result) { path.push_back(node-val); // 前序路径先记录当前节点 if (node-left nullptr node-right nullptr) { string s; for (int i 0; i path.size() - 1; i) { s to_string(path[i]) -; } s to_string(path[path.size() - 1]); result.push_back(s); return; // 叶子节点直接结算回到上一层再统一回溯 } if (node-left) { traversal(node-left, path, result); path.pop_back(); // 递归返回撤销左子树带来的状态 } if (node-right) { traversal(node-right, path, result); path.pop_back(); // 同理撤销右子树带来的状态 } } };解释一下为什么 pop_back 必须紧跟在递归调用后面。这里 path 是引用传递的整棵递归树共享同一个 vector。进入某个子节点前 push_back 一次递归返回后如果不清掉下一次进入兄弟节点时 path 里仍然留着上一个子树的值最终每条路径都会多出一截不属于自己的节点。另一个容易困惑的点叶子节点 push_back 之后没有立刻 pop_back谁负责清理答案是父节点。当 traversal(node-left) 返回时父节点那一层紧接着执行 path.pop_back()把叶子节点从 path 中弹掉。这个上层负责收回的约定是回溯递归里非常关键的设计——你把状态追加给别人你也要负责在返回后撤销。3.3 字符串传值的简化版省事但学不到回溯如果直接用 string 作为 path每次递归传值拷贝可以少写 pop_back代码短了很多class Solution { public: vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; dfs(root, , result); return result; } void dfs(TreeNode* node, string path, vectorstring result) { if (node nullptr) return; path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); return; } path -; dfs(node-left, path, result); dfs(node-right, path, result); } };这版本的回溯是隐式的——每次递归创建新的 string返回后旧变量自动作废状态自然恢复。逻辑简洁可读性也好257 题的数据范围节点数最多100完全跑得动。但我依然建议在训练阶段先写引用回溯的版本。原因很简单后面的回溯算法章节才是重头戏。组合、排列、子集这些问题里路径的状态不能依赖字符串值拷贝解决必须用引用 pop_back 手动维护。树的路径问题是练习这套技能最好的场景因为树的结构天然给了明确的进入和返回时机。你在 257 上练熟了push_back 递归 pop_back的节奏后面写 permutations 时会顺手很多。而且面试官如果追问为什么用引用传 path你能讲出因为要显式回溯避免兄弟子树之间的状态污染这比只交一个值拷贝版本更能体现对递归原理的理解。4. 404.左叶子之和判定条件要写在父节点上4.1 站在叶子上看不清自己是谁练完汇总110和传递257两种方向第三道题加了一点刁钻的细节。左叶子之和的题意直白把所有满足左叶子条件的节点值加起来。但左叶子这个词藏了一个初学者最容易掉进去的陷阱。左叶子需要同时满足两个条件它是一个叶子节点也就是没有左孩子也没有右孩子它是某个节点的左孩子。问题在于当你站在一个叶子节点上你完全没有信息判断自己是左孩子还是右孩子。你自己的视角里只有我是不是叶子没有我在父节点的哪一边。方向是相对父节点才存在的所以判断逻辑必须上移到父节点那一层——检查当前节点是否存在一个左孩子并且那个左孩子本身是叶子。这个站在父节点看子节点身份的思路是这类题目和普通遍历最大的差别。很多人卡在 404 上不是不会遍历而是思维没有完成从节点本位到关系本位的切换。树的很多条件判断都是关系性的左叶子是父子关系右视图是层级关系最近公共祖先也是祖先-后代关系。尽早建立这个视角后面读树题会轻松很多。4.2 判定逻辑怎么写三种遍历次序都能做递归实现上我推荐后序版本因为结构最统一class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; int leftSum sumOfLeftLeaves(root-left); int rightSum sumOfLeftLeaves(root-right); int cur 0; if (root-left root-left-left nullptr root-left-right nullptr) { cur root-left-val; // 左孩子是叶子它就是当前子树能贡献的左叶子 } return leftSum rightSum cur; } };这个函数的语义是返回以 node 为根的子树中所有左叶子的和。递归的三段分别是左子树里有多少左叶子右子树里有多少左叶子当前节点自己能不能额外贡献一个左叶子也就是它的左孩子是不是左叶子。注意一个边界成立条件是root-left root-left-left nullptr root-left-right nullptr三个条件一个都不能少。少了 root-left空指针解引用直接崩少了后面任何一个非叶子的左孩子也会被误算进来。这个三条件判断就是整道题唯一的考点写对它就通过了。后序版本里函数本身要返回子树的累加结果用哪种遍历顺序最终结果都一样。你可以试试把返回挪到递归之前就是前序版本同样能 AC。真正重要的只有那个判定条件的位置和完整性。如果偏好迭代用栈模拟前序完全没问题判定条件一字不差class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; stackTreeNode* st; st.push(root); int sum 0; while (!st.empty()) { TreeNode* node st.top(); st.pop(); if (node-left node-left-left nullptr node-left-right nullptr) { sum node-left-val; } if (node-right) st.push(node-right); if (node-left) st.push(node-left); } return sum; } };迭代版每次从栈里弹出一个节点马上检查它有没有左叶子孩子有就加上。栈的顺序不影响结果因为每条边都只会被它的父节点检视一次左叶子的判定天然和遍历顺序无关。5. 222.完全二叉树的节点个数别把特殊树当普通树刷5.1 完全二叉树的结构红利在哪到了第四题场景再次改变——不再强调遍历顺序而是强调结构认知。完全二叉树的定义很严格除最后一层外每一层的节点数都是满的最后一层的节点全部靠左排列。拿这个定义对比普通二叉树你会发现完全二叉树的形状被约束得非常死而这种约束正是优化的机会。最朴素的解法是暴力数递归遍历每个节点O(n)。n 如果只有几千这题明显能过——LeetCode 当前给的节点数上限是 5×10⁴暴力也不超时。但题目既然特意告诉你这是完全二叉树就说明出题人期望你利用它。关键观察是如果从某个节点出发沿着最左路径走到底的深度和沿着最右路径走到底的深度相等那么以这个节点为根的子树一定是一棵满二叉树——每一层都填满了。满二叉树的节点总数可以直接用公式层数为 h 时节点数等于 2^h - 1。这样一整棵满子树就不需要逐个节点去访问了。算法可以这样设计每到一个节点先量一量左右边界深度如果相等说明整棵子树是满的套公式直接返回如果不等说明当前子树没有填满继续往左右子树递归。递归到某个深度时遇到满子树就停住用公式收割结果。5.2 完整代码与复杂度推导class Solution { public: int countNodes(TreeNode* root) { if (root nullptr) return 0; int leftDepth 0, rightDepth 0; TreeNode* leftNode root-left; TreeNode* rightNode root-right; while (leftNode) { // 沿着最左路径往下走数边数 leftNode leftNode-left; leftDepth; } while (rightNode) { // 沿着最右路径往下走数边数 rightNode rightNode-right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; // 等价于 2^(leftDepth1) - 1 } return 1 countNodes(root-left) countNodes(root-right); } };解释一下位运算。leftDepth 统计的是从当前节点的左孩子一路往左下走的边数。如果左右深度相等当前子树的层数是 leftDepth 1满二叉树的节点数就是 2^(leftDepth1) - 1。2 leftDepth就是把 2 左移 leftDepth 位相当于 2^(leftDepth1)所以(2 leftDepth) - 1就是这个公式的紧凑写法。如果不习惯位运算写成(1 (leftDepth 1)) - 1更直白。用一棵 6 个节点的完全二叉树走一遍流程根节点下有左子 L、右子 RL 有两个孩子 LL、LRR 有一个孩子 RL。在根节点左边界路径是 L→LLleftDepth 2右边界路径是 RRL 的右侧没有节点rightDepth 1。不相等不能套公式。递归左子树 L以 L 为根有 LL、LR 两个满孩子leftDepth 1rightDepth 1相等按公式直接返回 3 个节点2² - 1 3不用往下走了。递归右子树 R以 R 为根只有一个左孩子 RL没有右孩子leftDepth 1rightDepth 0不相等。继续递归到 RL左右深度都为 0返回 1R 的右孩子为 null返回 0。所以 R 子树总数为 1 1 0 2。整个树的总数 根自身的 1 左子树 3 右子树 2 6。这个例子很直接地展示了优化效果整棵左子树只量了两次深度就立刻出结果没有逐个节点访问右子树也算是最小规模的递归。真正的大数据量下这个剪枝能省掉大量无效遍历。复杂度分析每次进入节点都需要花 O(h) 的时间测量左右边界深度。对于一个完全二叉树递归到某个节点后左右子树中至少有一个是满的可以直接用公式返回因此需要继续递归的分支会迅速减少。总的递归深度是 O(log n)每个递归层级上的测量总耗时也不会超过 O(log n)所以整体的时间复杂度是 O(log²n)空间复杂度是递归栈的 O(log n)。5.3 暴力解虽然能过为什么还要学优化我知道很多人刷这道题时会有疑问LeetCode 上节点数上限是 5×10⁴直接写 count(root) count(root-left) count(root-right) 1 也能 AC为什么要费劲学这个满二叉树公式版本我从训练营和面试两个角度说下自己的理解。从训练营的角度这四道题是一个递进。前面几道题练的是如何把遍历用好222 练的是如何看出可以用数学跳步。如果你只满足于 AC 一个暴力解那这一天的最后一题就没有任何增量价值。真正值得吸收的是观察结构性质 → 把性质变成剪枝条件 → 用公式接管重复劳动这个思维链路。从面试的角度出了这题面试官真正想看的不是你数节点数数得快而是你会不会利用题面已经告诉你的完全二叉树这个性质。你在面试里如果主动说我可以先暴力 O(n) 保底然后再用满二叉树公式优化到 O(log²n)传递出来的信号是我不只会写模板我还会针对数据结构特性做复杂度分析。这种信号在很多场景下比 AC 本身更有价值。当然暴力解也有存在意义——它是你思路断掉时的兜底。我自己的习惯是先确保暴力解不出错再在暴力解的基础上加剪枝。这样即使优化部分写错了至少能保底拿分。6. 常见问题与排查技巧实录6.1 四道题最容易踩的坑一览我把实际刷题时收集到的坑整理成一个速查表每一个都是真实发生过的题目典型错误症状正确做法110混淆深度和高度用前序累计深度判断平衡高度走后序从子树结果推自身110每个节点重复算高度极端数据超时单次后序 -1 哨兵257忘记回溯左右子树路径互相污染递归返回后立即 pop_back257叶子节点仍继续递归空子树也被加入路径叶子节点直接结算路径并 return404判定条件少写右孩子检查左子树内部节点被当左叶子三个条件一个都不能少404站在叶子节点判断自己无法知道自己是不是左孩子把判断写到父节点222不利用满二叉树公式暴力遍历能过但无增量左右深度相等时直接套公式222位运算写错2 leftDepth 误写为 1 leftDepth换算成 2^(leftDepth1)-1 检查除了表里这些还有一个很隐蔽的细节110 的剪枝不完整。有人写了 -1 哨兵但在拿到 leftHeight 之后没有立刻检查而是继续调 rightHeight。这在语义上没错但浪费了一次递归。正确写法是拿到左子树结果先判断一次拿到右子树结果再判断一次见 -1 就立刻 return把剪枝效果做满。257 的字符串拼接也容易出格式问题。如果每一层都先把 - 拼在节点值后面最后一个叶子的值后面会多出一个 -。我常用的规避方法是像上面的代码那样到叶子统一拼接或者先收集到 vector 里到叶子再统一格式化。别在中间步骤贪图省事。222 的溢出问题也值得提一句。虽然当前数据范围不会触发但(2 leftDepth)在 leftDepth 较大时会超过 32 位 int 的上界。面试时可以主动提一句这里用 long long 更稳这是加分项。6.2 递归调试三板斧树的递归题我调试用的是三个土办法实测比纯看代码快很多。第一招打印递归轨迹。在函数入口打印节点值和当前递归深度在返回前打印返回值。可以用一个字符串把深度可视化void debug(TreeNode* node, int depth) { if (node nullptr) return; cout string(depth * 2, -) node-val endl; debug(node-left, depth 1); debug(node-right, depth 1); }这个缩进输出能直接看出递归的进入和返回顺序特别适合排查 257 这类路径问题——你能肉眼看到路径是在哪里被错误保留、在哪里被错误弹掉的。第二招准备一组最小的边界用例。树的题边界用例其实非常固定空树、只有一个节点的树、左斜树、右斜树、满二叉树、完全但不满的树。每道题刷完把这几个用例跑一遍基本能把隐藏 bug 全部暴露出来。比如 404 的判定用一棵三节点的树根 左叶 右叶就能立刻验证左叶子有没有被正确累加。第三招递归和迭代互验。同一道题分别写递归和迭代版本用随机生成的树跑对比。如果两个版本结果不一致通常问题出在遍历顺序或者状态恢复的时机上。这个办法对 257 尤其管用因为回溯阶段的时机错误很容易被版本间的差异暴露出来。提示刷树题最忌讳的是盯着代码空想。我一般建议先画一棵不超过四层的小树把递归的调用顺序在纸上推一遍再去和代码的打印结果对。纸上能推对代码基本就不会错。最后分享一点我自己的体会。刷完第13天这四道题我最大的变化不是记住了四个模板而是形成了一个新的思考习惯每个树题读完我会先问自己三个问题——当前节点要从子节点拿到什么信息当前节点自己要贡献什么信息这些信息该往上返回还是往下传给子节点110 要的是从子节点拿高度和合法性257 要的是把路径往下传给子节点404 是要从子节点拿求和结果、同时自己判断左叶子222 则是要从子节点拿节点数但同时利用满树公式跳过计算。一旦这三个问题想清楚代码怎么写几乎是水到渠成的事。这也是训练营这个阶段最值钱的东西——不是在练代码是在练建模。如果你也在这四道题上反复卡壳别急着看题解先把上面三个问题写在纸上想明白再动手效果会比背十遍题解都好。