1. 刷题前先理清主线这四道题到底在考什么第23天打卡我挑了四道二叉树题目平衡二叉树、二叉树的所有路径、左叶子之和、找树左下角的值。如果你最近也在集中刷C算法题你会发现这四道题是很好的递归四件套练习它们分别考察了树的高度计算与剪枝、前序遍历收集路径、基于父子关系的条件判断、以及层序和前序的变体应用。题号都不算难题但每道题都有值得深挖的细节尤其对刚接触二叉树的同学来说把这几道题吃透后面刷二叉树相关的综合题会顺畅很多。我先把这四道题在思维层面做个归类平衡二叉树考的是递归返回值怎么设计二叉树的所有路径考的是递归过程中如何携带并恢复状态左叶子之和考的是判断条件放在哪个节点上找树左下角的值考的则是BFS和DFS在最值场景下的取舍。四道题表面上是四个独立问题底层却共用同一套递归思考框架。所以这篇文章不只是贴四份代码而是想把每道题背后的选择逻辑讲清楚为什么用这个遍历顺序为什么这么设计返回值什么时候该回溯什么时候不需要。这次用的是C写环境就是VS Code C17刷题写函数对应LeetCode的类接口。代码风格我偏好把辅助函数单独抽出来主函数保持干净这样调试的时候能很清楚看到递归的入口和出口。四道题我都先自己跑了一遍本地用例再贴到LeetCode提交途中也踩了不少坑比如平衡二叉树那个-1哨兵值一开始没想明白所有路径那道题路径字符串回溯时多拼了一个箭头这些细节下面都会展开说。2. 平衡二叉树从O(n^2)到O(n)的递归优化2.1 题目描述到底在问什么平衡二叉树Balanced Binary Tree的定义是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。注意这里说的是每个节点不只是根节点。也就是说即使根节点左右子树高度差是1如果某个子树的内部出现了不平衡整棵树依然不算平衡二叉树。理解这个定义是这题的第一道门槛因为很多第一次做这题的人会想当然地只算一次根节点的左右子树高度差然后发现用例不过回头一看才发现每个节点四个字才是真正的判定条件。我自己的做法是拿到题目先把定义换成数学描述对任意节点|height(left) - height(right)| 1并且左子树平衡并且右子树平衡。这个描述写出来之后递归结构其实已经呼之欲出了。2.2 自顶向下递归思路直观但性能拉跨最容易想到的解法是自顶向下递归class Solution { public: 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 leftH getHeight(root-left); int rightH getHeight(root-right); return abs(leftH - rightH) 1 isBalanced(root-left) isBalanced(root-right); } };这段代码逻辑完全正确但性能不够好。我算了一下复杂度每调用一次isBalanced都要调用一次getHeight而getHeight会遍历当前子树的所有节点。假设二叉树节点数是n在最坏情况比如一棵非常倾斜的树下每个节点作为根的时候都要算一遍高度每个高度计算又都需要遍历到叶子节点总的时间复杂度是O(n^2)。虽然LeetCode上这题的数据量不大自顶向下也能过但刷题不能只看能过还要理解为啥有更优的做法。2.3 自底向上递归让高度和是否平衡一起返回我在第二次尝试时换成了自底向上的思路。核心想法是在后序遍历的过程中子树一旦发现不平衡就返回一个特殊值然后逐层向上传递不再继续做无意义的计算。这里我用-1作为已经不平衡的哨兵值class Solution { public: int getHeightOrUnbalanced(TreeNode* node) { if (node nullptr) return 0; int leftH getHeightOrUnbalanced(node-left); if (leftH -1) return -1; int rightH getHeightOrUnbalanced(node-right); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return max(leftH, rightH) 1; } bool isBalanced(TreeNode* root) { return getHeightOrUnbalanced(root) ! -1; } };这段代码的思想是每个节点在递归返回时只做两件事第一检查左右子树是否已经返回-1如果是就直接往上抛-1不再继续第二比较左右子树高度差如果超过1说明当前节点已经不满足平衡条件也返回-1。只有左右子树都平衡且高度差不超过1时才返回当前子树的高度。这里有一点要注意哨兵值的选取。为什么用-1因为二叉树的高度永远不会是负数空节点高度是0叶子节点高度是1所以-1是一个绝对安全的非法值。如果你担心-1和真实高度撞车这是不会发生的因为正常递归路径上任何节点的高度都不可能返回-1只有异常情况才会返回-1。这个设计有点像网络中传输协议的魔术数字用来标识特殊状态。2.4 为什么自底向上能把复杂度降到O(n)自底向上的关键在于每个节点在递归过程中只被访问一次。后序遍历保证了先处理完左右子树再回到当前节点。当子树不平衡时通过-1哨兵层层返回上层节点检测到-1后直接剪枝避免后续的高度重复计算。我实际测试下来自底向上的耗时大概是自顶向下的五分之一左右。在数据量较大的情况下差别很明显。这也是一道非常典型的遍历一遍解决问题的题面试时如果只写出自顶向下的版本在后面的追问中往往会被要求优化。能够主动说出自底向上的思路并用-1哨兵值实现是一个很大的加分项。实操中有个细节我踩过坑max(leftH, rightH) 1之前必须先判断两个子树是否为-1。如果你先算高度差再判断是否有-1就会出bug。因为如果rightH已经是-1abs(leftH - rightH)算出来的结果可能大于1可能返回-1看起来也对但这会掩盖一个潜在问题-1参与了高度差计算容易在复杂的树结构下产生不可预期的结果。我的建议是把-1的判断放在最前面形成短路逻辑这样代码的意图更清晰。3. 二叉树的所有路径回溯与状态恢复3.1 题目与DFS直觉二叉树的所有路径Binary Tree Paths要求返回所有从根节点到叶子节点的路径每条路径用-分隔节点值。比如一棵简单的树1 / \ 2 3 \ 5返回结果是[1-2-5, 1-3]。这题的核心是DFS因为要找的是从根到叶子的完整路径天然适合深度优先遍历。我选择前序遍历先处理当前节点把值加入路径找到叶子节点时记录整条完整路径然后继续向左右子树延伸。但这题真正考验人的是路径状态的恢复。递归到某个分支结束后路径需要回到上一层的状态否则会错误地带着已经访问过的节点值去探索兄弟分支。这个状态恢复在算法里叫回溯。3.2 隐式回溯靠值传递自动恢复C里最简单的写法是利用值传递。因为path是按值传入的每次函数调用持有的都是当前路径的一个副本函数返回后上一层的path完全不受影响天然实现了回溯。class Solution { public: void dfs(TreeNode* node, string path, vectorstring result) { path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); return; } if (node-left) { dfs(node-left, path -, result); } if (node-right) { dfs(node-right, path -, result); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; dfs(root, , result); return result; } };注意path -这一句它创建了一个新字符串传入下一层递归但当前层的path没有改变。这样当下层递归返回后当前层的path仍然是上一轮状态不需要手动删除任何字符。这就是隐式回溯的巧妙之处。3.3 显式回溯引用传递时的手动恢复如果出于性能考虑想把字符串的拷贝开销省掉可以使用引用传递但必须手动恢复状态。写出来是下面这样class Solution { public: void dfs(TreeNode* node, string path, vectorstring result) { path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); } else { if (node-left) { path -; dfs(node-left, path, result); path.pop_back(); // 删除 path.pop_back(); // 删除 - } if (node-right) { path -; dfs(node-right, path, result); path.pop_back(); path.pop_back(); } } int len to_string(node-val).size(); while (len--) { path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; string path; dfs(root, path, result); return result; } };这段代码在恢复路径时非常繁琐既要删除-两个字符又要处理数字的位数。我觉得在刷题阶段完全没有必要为了省那点拷贝开销写这种容易出bug的代码。但显式回溯的思维模式很重要因为很多题目比如全排列、组合总和用引用传递是主流写法路径恢复必须手动完成。这道题用值传递写能帮你先建立不需要手动恢复的直觉后面遇到必须用引用的题时再掌握手动回溯也不迟。3.4 这题的几个坑我实际提交中碰到的问题有这几个第一忘记判断叶子节点。如果只判断node nullptr就返回路径会在叶子节点的空子树上重复记录导致结果出现重复路径。第二空树直接返回空数组。LeetCode的测试用例里有空树root为nullptr如果不加特判访问root-val会直接崩掉。第三数字转字符串。C里不能用C语言的itoa这不是标准库函数要使用to_string。另外有同学喜欢先to_string再 -最后整体判断我是觉得把箭头拼进递归参数里更简洁。从这道题里我总结出一个通用经验凡是收集所有路径类的DFS题目优先考虑值传递加隐式回溯写出正确代码后再考虑优化凡是只找一条路径类的题目通常用引用传递配合布尔返回值找到就剪枝返回。这两种模式刷多了自然就分清了。4. 左叶子之和判断条件放在父节点上4.1 左叶子的定义陷阱左叶子之和Sum of Left Leaves要求计算所有左叶子节点的值之和。什么是左叶子我一开始的理解是左边还没有叶子节点的节点但实际上定义有两层第一它必须是一个叶子节点即左右孩子都为空第二它必须是其父节点的左孩子。有人可能会觉得直接对每个节点判断自己是叶子且是左孩子不就行了吗问题在于递归函数里的当前节点根本不知道自己是左孩子还是右孩子。二叉树节点只有左右指针没有指向父节点的指针。所以正确的做法是在父节点这一层做判断如果当前节点的左孩子不为空且左孩子的左右孩子都为空那么当前节点的左孩子就是一个左叶子。用代码描述这个逻辑node-left ! nullptr node-left-left nullptr node-left-right nullptr这个条件看起来简单但它是整个题的核心。很多第一次刷这题的人会把判断写成当前节点是叶子且当前节点是左孩子然后发现无法实现原因就是缺了父节点视角。4.2 递归实现后序遍历的经典场景这题适合后序遍历因为求和需要先把左右子树的结果算出来再往上传。你也可以用前序遍历但后序遍历的代码结构和先收集再合并的思维最贴合。class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 0; int leftSum sumOfLeftLeaves(root-left); if (root-left ! nullptr root-left-left nullptr root-left-right nullptr) { leftSum root-left-val; } int rightSum sumOfLeftLeaves(root-right); return leftSum rightSum; } };代码里有个细节我一开始没注意在递归计算左子树的和之后还要再判断一次当前节点的左孩子是否是左叶子如果是就直接用左孩子的值覆盖leftSum。为什么可以覆盖因为后序遍历已经处理完了左子树内部的所有左叶子如果左孩子本身是左叶子那么它内部不可能再有子节点leftSum必须等于这个叶子值如果左孩子不是左叶子leftSum就是左子树内部所有左叶子的和不需要覆盖。这个先递归再覆盖的双步判断是这题的精髓也特别容易在代码review时被忽略。我写第一版时漏掉了覆盖结果根节点的左孩子是左叶子时它的值怎么也进不了总和。4.3 迭代法用栈模拟后序遍历如果你不想用递归也可以用栈做迭代。思路和递归一致只是把递归入口换成栈操作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 ! nullptr node-left-left nullptr node-left-right nullptr) { sum node-left-val; } if (node-left) st.push(node-left); if (node-right) st.push(node-right); } return sum; } };这个迭代版本用前序遍历的顺序也能做因为判断左叶子只依赖父节点和祖父节点的关系和遍历顺序没有强绑定。我在本地跑了几组用例迭代和递归结果一致。面试时如果先写了递归再补一个迭代写法能体现你对树的遍历框架掌握得比较全面。5. 找树左下角的值BFS的经典变体5.1 题目解读与两种思路找树左下角的值Find Bottom Left Tree Value要求返回二叉树最底层最左边节点的值。注意是最底层且最左边两者都要满足。如果最底层只有一个节点那它就是答案如果最底层有多个节点答案是这一层最左边的那个。这题有两种主流解法BFS层序遍历和DFS深度优先。我第一次想到的是BFS因为层序天然一层一层扫描记录每一层的第一个节点值扫描完整棵树后这个值自然就是最后一层的最左值。5.2 最直观的层序遍历记录每层第一个节点class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* que; que.push(root); int result root-val; while (!que.empty()) { int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (i 0) { result node-val; } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return result; } };这个版本的思路是用size控制每一层的节点数i 0表示该层第一个节点。每处理完一层result就被更新成当前层的最左值。当队列为空时最后一次更新的result就是最底层最左值。这个写法很直观不会有任何歧义适合作为基础版本。5.3 从右往左入队一个更简洁的经典技巧如果你希望代码更短一点有一个经典技巧BFS时先把右孩子入队再把左孩子入队那么最后一个出队的节点一定是最底层最左边的节点。代码是这样的class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* que; que.push(root); int result root-val; while (!que.empty()) { TreeNode* node que.front(); que.pop(); if (node-right) que.push(node-right); if (node-left) que.push(node-left); result node-val; } return result; } };为什么这样写是对的因为队列是先进先出。如果我们一直先推右再推左那么同一层中左边的节点会比右边的节点更晚出队。整个BFS过程中最先出队的是根节点最后出队的必然是整棵树最末尾访问到的节点。由于同一层是从右往左入队、从右往左出队也就是说同一层左边的节点比右边的晚出队所以最后出队的节点是同一层最左边的节点。又因为BFS是逐层进行的最后一层才是在队列中最后被处理的层两者一结合最后出队的节点就是最底层最左边的节点。这个技巧我第一次看的时候觉得有点绕但实测跑两次就懂了。它把记录每层第一个节点这个条件化逻辑变成了记录出队过的最后一个节点这种无条件逻辑代码更简洁但可读性稍有下降。我建议先理解5.2的基础写法再在这个基础上优化不要一上来就用技巧否则容易看不懂自己的代码。5.4 递归解法最大深度 前序遍历如果你更习惯DFS这题也可以用递归做。思路是维护一个最大深度同时前序遍历树。前序遍历天然先访问左子树再访问右子树所以第一次到达更大深度时遇到的节点一定是该层最左边的节点。class Solution { public: int maxDepth -1; int result 0; void dfs(TreeNode* node, int depth) { if (node nullptr) return; if (node-left nullptr node-right nullptr) { if (depth maxDepth) { maxDepth depth; result node-val; } return; } dfs(node-left, depth 1); dfs(node-right, depth 1); } int findBottomLeftValue(TreeNode* root) { dfs(root, 0); return result; } };这里的关键点在于判断叶子节点并且只更新第一个到达新深度的叶子。由于前序遍历是先左后右同一深度下左叶子会先被访问到。所以当遇到一个叶子节点的深度大于maxDepth时它一定是这一层第一个被访问的节点也就是最左边的节点。递归解法的空间复杂度在最坏情况下是O(n)退化成链表而BFS的空间复杂度是O(n)队列中最多存放一层的节点。两者大差不差但递归写法更符合二叉树题优先递归的思维习惯。我刷题时两种写法都会面试时如果面试官问能不能不用BFS做递归解法就是很好的备份方案。5.5 BFS和DFS的对比心得在这道题上BFS的直观性更强因为它天然逐层扫描而DFS需要额外记录深度信息来判断最左。但从通用性来说DFS在搜索一条路径的场景下更强BFS在逐层处理的场景下更强。这两种遍历框架是二叉树题的两大底座把这题的两种解法都写一遍对理解两者的边界非常有帮助。6. 打卡总结四道题背后的四个思维模型6.1 四道题的思维模型对比这四道题刷完之后我在笔记里给它们各打了一个标签用来提醒自己以后遇到同类型题目时往哪想平衡二叉树返回值设计。需要同时返回是否合法和高度时可以用一个非法值作为哨兵。对应更复杂的场景是判断二叉树是否对称、是否二叉搜索树等都可以用类似的自底向上思路。二叉树的所有路径回溯。收集从根到叶子的所有路径时值传递可以免去手动回溯但必须理解隐式回溯的原理。对应场景是打印根到指定节点的路径、求路径和等。左叶子之和条件判断的位置。判断一个节点是否是左叶子必须站在父节点的角度看。对应场景是求二叉树的所有叶子节点、求右叶子之和等。找树左下角的值遍历顺序的变化。BFS从右往左入队的变形让最左这个条件自然满足。对应场景是找最右叶子、找最靠近某个值的节点等。我把这四类问题放到一张表里题目核心考点主要解法关键易错点平衡二叉树递归返回值设计自底向上 -1哨兵只判断根节点高度差二叉树的所有路径回溯前序遍历 值传递忘记叶子节点判断左叶子之和父子关系判断后序遍历从自身角度判断左叶子找树左下角的值遍历顺序与技巧BFS从右往左入队混淆最底层与最左6.2 我的刷题心得与建议这四道题刷新完我觉得最值得反复练习的是平衡二叉树和二叉树的所有路径。前者训练递归返回值的设计能力后者训练回溯的状态感知能力。这两个能力是二叉树递归题目的两个关键支点很多更复杂的题目都是从这两个支点延伸出来的。我个人的习惯是每道题先自己用底纸画一遍示例树的递归过程标出每个入口和出口的高度值或路径字符串再去看代码。这样能直观地看到-1是怎么向上传播的路径字符串是怎么在递归返回后恢复的。画完一遍之后很多为什么就变得不用背了。另外有一点经验可以分享给你刷题打卡这件事重点不是每天刷多少题而是每道题之后有没有留下属于自己的复盘。哪怕只有三行笔记过两周再翻出来看都能快速唤醒记忆。这四道题我建议你按顺序刷先做平衡二叉树理解返回值设计再做二叉树的所有路径理解回溯接着做左叶子之和体会判断条件的位置最后做找树左下角的值感受遍历顺序带来的简化。按这个顺序递进思维链路是连贯的不会觉得每道题都是孤立的。最后说一个很多人容易忽略的小点这些题在LeetCode上都有官方题解但官方题解往往只给最优思路不会告诉你第一次写容易踩什么坑。刷题的过程中把自己错误的版本保存下来对比正确版本比单纯抄一遍标准答案有用得多。我就是习惯把每次的报错用例和错误代码存进注释里这样每次提交前扫一眼能少踩很多重复的坑。
刷透二叉树：平衡、路径、左叶子与左下角的递归思维
1. 刷题前先理清主线这四道题到底在考什么第23天打卡我挑了四道二叉树题目平衡二叉树、二叉树的所有路径、左叶子之和、找树左下角的值。如果你最近也在集中刷C算法题你会发现这四道题是很好的递归四件套练习它们分别考察了树的高度计算与剪枝、前序遍历收集路径、基于父子关系的条件判断、以及层序和前序的变体应用。题号都不算难题但每道题都有值得深挖的细节尤其对刚接触二叉树的同学来说把这几道题吃透后面刷二叉树相关的综合题会顺畅很多。我先把这四道题在思维层面做个归类平衡二叉树考的是递归返回值怎么设计二叉树的所有路径考的是递归过程中如何携带并恢复状态左叶子之和考的是判断条件放在哪个节点上找树左下角的值考的则是BFS和DFS在最值场景下的取舍。四道题表面上是四个独立问题底层却共用同一套递归思考框架。所以这篇文章不只是贴四份代码而是想把每道题背后的选择逻辑讲清楚为什么用这个遍历顺序为什么这么设计返回值什么时候该回溯什么时候不需要。这次用的是C写环境就是VS Code C17刷题写函数对应LeetCode的类接口。代码风格我偏好把辅助函数单独抽出来主函数保持干净这样调试的时候能很清楚看到递归的入口和出口。四道题我都先自己跑了一遍本地用例再贴到LeetCode提交途中也踩了不少坑比如平衡二叉树那个-1哨兵值一开始没想明白所有路径那道题路径字符串回溯时多拼了一个箭头这些细节下面都会展开说。2. 平衡二叉树从O(n^2)到O(n)的递归优化2.1 题目描述到底在问什么平衡二叉树Balanced Binary Tree的定义是一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。注意这里说的是每个节点不只是根节点。也就是说即使根节点左右子树高度差是1如果某个子树的内部出现了不平衡整棵树依然不算平衡二叉树。理解这个定义是这题的第一道门槛因为很多第一次做这题的人会想当然地只算一次根节点的左右子树高度差然后发现用例不过回头一看才发现每个节点四个字才是真正的判定条件。我自己的做法是拿到题目先把定义换成数学描述对任意节点|height(left) - height(right)| 1并且左子树平衡并且右子树平衡。这个描述写出来之后递归结构其实已经呼之欲出了。2.2 自顶向下递归思路直观但性能拉跨最容易想到的解法是自顶向下递归class Solution { public: 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 leftH getHeight(root-left); int rightH getHeight(root-right); return abs(leftH - rightH) 1 isBalanced(root-left) isBalanced(root-right); } };这段代码逻辑完全正确但性能不够好。我算了一下复杂度每调用一次isBalanced都要调用一次getHeight而getHeight会遍历当前子树的所有节点。假设二叉树节点数是n在最坏情况比如一棵非常倾斜的树下每个节点作为根的时候都要算一遍高度每个高度计算又都需要遍历到叶子节点总的时间复杂度是O(n^2)。虽然LeetCode上这题的数据量不大自顶向下也能过但刷题不能只看能过还要理解为啥有更优的做法。2.3 自底向上递归让高度和是否平衡一起返回我在第二次尝试时换成了自底向上的思路。核心想法是在后序遍历的过程中子树一旦发现不平衡就返回一个特殊值然后逐层向上传递不再继续做无意义的计算。这里我用-1作为已经不平衡的哨兵值class Solution { public: int getHeightOrUnbalanced(TreeNode* node) { if (node nullptr) return 0; int leftH getHeightOrUnbalanced(node-left); if (leftH -1) return -1; int rightH getHeightOrUnbalanced(node-right); if (rightH -1) return -1; if (abs(leftH - rightH) 1) return -1; return max(leftH, rightH) 1; } bool isBalanced(TreeNode* root) { return getHeightOrUnbalanced(root) ! -1; } };这段代码的思想是每个节点在递归返回时只做两件事第一检查左右子树是否已经返回-1如果是就直接往上抛-1不再继续第二比较左右子树高度差如果超过1说明当前节点已经不满足平衡条件也返回-1。只有左右子树都平衡且高度差不超过1时才返回当前子树的高度。这里有一点要注意哨兵值的选取。为什么用-1因为二叉树的高度永远不会是负数空节点高度是0叶子节点高度是1所以-1是一个绝对安全的非法值。如果你担心-1和真实高度撞车这是不会发生的因为正常递归路径上任何节点的高度都不可能返回-1只有异常情况才会返回-1。这个设计有点像网络中传输协议的魔术数字用来标识特殊状态。2.4 为什么自底向上能把复杂度降到O(n)自底向上的关键在于每个节点在递归过程中只被访问一次。后序遍历保证了先处理完左右子树再回到当前节点。当子树不平衡时通过-1哨兵层层返回上层节点检测到-1后直接剪枝避免后续的高度重复计算。我实际测试下来自底向上的耗时大概是自顶向下的五分之一左右。在数据量较大的情况下差别很明显。这也是一道非常典型的遍历一遍解决问题的题面试时如果只写出自顶向下的版本在后面的追问中往往会被要求优化。能够主动说出自底向上的思路并用-1哨兵值实现是一个很大的加分项。实操中有个细节我踩过坑max(leftH, rightH) 1之前必须先判断两个子树是否为-1。如果你先算高度差再判断是否有-1就会出bug。因为如果rightH已经是-1abs(leftH - rightH)算出来的结果可能大于1可能返回-1看起来也对但这会掩盖一个潜在问题-1参与了高度差计算容易在复杂的树结构下产生不可预期的结果。我的建议是把-1的判断放在最前面形成短路逻辑这样代码的意图更清晰。3. 二叉树的所有路径回溯与状态恢复3.1 题目与DFS直觉二叉树的所有路径Binary Tree Paths要求返回所有从根节点到叶子节点的路径每条路径用-分隔节点值。比如一棵简单的树1 / \ 2 3 \ 5返回结果是[1-2-5, 1-3]。这题的核心是DFS因为要找的是从根到叶子的完整路径天然适合深度优先遍历。我选择前序遍历先处理当前节点把值加入路径找到叶子节点时记录整条完整路径然后继续向左右子树延伸。但这题真正考验人的是路径状态的恢复。递归到某个分支结束后路径需要回到上一层的状态否则会错误地带着已经访问过的节点值去探索兄弟分支。这个状态恢复在算法里叫回溯。3.2 隐式回溯靠值传递自动恢复C里最简单的写法是利用值传递。因为path是按值传入的每次函数调用持有的都是当前路径的一个副本函数返回后上一层的path完全不受影响天然实现了回溯。class Solution { public: void dfs(TreeNode* node, string path, vectorstring result) { path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); return; } if (node-left) { dfs(node-left, path -, result); } if (node-right) { dfs(node-right, path -, result); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; dfs(root, , result); return result; } };注意path -这一句它创建了一个新字符串传入下一层递归但当前层的path没有改变。这样当下层递归返回后当前层的path仍然是上一轮状态不需要手动删除任何字符。这就是隐式回溯的巧妙之处。3.3 显式回溯引用传递时的手动恢复如果出于性能考虑想把字符串的拷贝开销省掉可以使用引用传递但必须手动恢复状态。写出来是下面这样class Solution { public: void dfs(TreeNode* node, string path, vectorstring result) { path to_string(node-val); if (node-left nullptr node-right nullptr) { result.push_back(path); } else { if (node-left) { path -; dfs(node-left, path, result); path.pop_back(); // 删除 path.pop_back(); // 删除 - } if (node-right) { path -; dfs(node-right, path, result); path.pop_back(); path.pop_back(); } } int len to_string(node-val).size(); while (len--) { path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorstring result; if (root nullptr) return result; string path; dfs(root, path, result); return result; } };这段代码在恢复路径时非常繁琐既要删除-两个字符又要处理数字的位数。我觉得在刷题阶段完全没有必要为了省那点拷贝开销写这种容易出bug的代码。但显式回溯的思维模式很重要因为很多题目比如全排列、组合总和用引用传递是主流写法路径恢复必须手动完成。这道题用值传递写能帮你先建立不需要手动恢复的直觉后面遇到必须用引用的题时再掌握手动回溯也不迟。3.4 这题的几个坑我实际提交中碰到的问题有这几个第一忘记判断叶子节点。如果只判断node nullptr就返回路径会在叶子节点的空子树上重复记录导致结果出现重复路径。第二空树直接返回空数组。LeetCode的测试用例里有空树root为nullptr如果不加特判访问root-val会直接崩掉。第三数字转字符串。C里不能用C语言的itoa这不是标准库函数要使用to_string。另外有同学喜欢先to_string再 -最后整体判断我是觉得把箭头拼进递归参数里更简洁。从这道题里我总结出一个通用经验凡是收集所有路径类的DFS题目优先考虑值传递加隐式回溯写出正确代码后再考虑优化凡是只找一条路径类的题目通常用引用传递配合布尔返回值找到就剪枝返回。这两种模式刷多了自然就分清了。4. 左叶子之和判断条件放在父节点上4.1 左叶子的定义陷阱左叶子之和Sum of Left Leaves要求计算所有左叶子节点的值之和。什么是左叶子我一开始的理解是左边还没有叶子节点的节点但实际上定义有两层第一它必须是一个叶子节点即左右孩子都为空第二它必须是其父节点的左孩子。有人可能会觉得直接对每个节点判断自己是叶子且是左孩子不就行了吗问题在于递归函数里的当前节点根本不知道自己是左孩子还是右孩子。二叉树节点只有左右指针没有指向父节点的指针。所以正确的做法是在父节点这一层做判断如果当前节点的左孩子不为空且左孩子的左右孩子都为空那么当前节点的左孩子就是一个左叶子。用代码描述这个逻辑node-left ! nullptr node-left-left nullptr node-left-right nullptr这个条件看起来简单但它是整个题的核心。很多第一次刷这题的人会把判断写成当前节点是叶子且当前节点是左孩子然后发现无法实现原因就是缺了父节点视角。4.2 递归实现后序遍历的经典场景这题适合后序遍历因为求和需要先把左右子树的结果算出来再往上传。你也可以用前序遍历但后序遍历的代码结构和先收集再合并的思维最贴合。class Solution { public: int sumOfLeftLeaves(TreeNode* root) { if (root nullptr) return 0; if (root-left nullptr root-right nullptr) return 0; int leftSum sumOfLeftLeaves(root-left); if (root-left ! nullptr root-left-left nullptr root-left-right nullptr) { leftSum root-left-val; } int rightSum sumOfLeftLeaves(root-right); return leftSum rightSum; } };代码里有个细节我一开始没注意在递归计算左子树的和之后还要再判断一次当前节点的左孩子是否是左叶子如果是就直接用左孩子的值覆盖leftSum。为什么可以覆盖因为后序遍历已经处理完了左子树内部的所有左叶子如果左孩子本身是左叶子那么它内部不可能再有子节点leftSum必须等于这个叶子值如果左孩子不是左叶子leftSum就是左子树内部所有左叶子的和不需要覆盖。这个先递归再覆盖的双步判断是这题的精髓也特别容易在代码review时被忽略。我写第一版时漏掉了覆盖结果根节点的左孩子是左叶子时它的值怎么也进不了总和。4.3 迭代法用栈模拟后序遍历如果你不想用递归也可以用栈做迭代。思路和递归一致只是把递归入口换成栈操作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 ! nullptr node-left-left nullptr node-left-right nullptr) { sum node-left-val; } if (node-left) st.push(node-left); if (node-right) st.push(node-right); } return sum; } };这个迭代版本用前序遍历的顺序也能做因为判断左叶子只依赖父节点和祖父节点的关系和遍历顺序没有强绑定。我在本地跑了几组用例迭代和递归结果一致。面试时如果先写了递归再补一个迭代写法能体现你对树的遍历框架掌握得比较全面。5. 找树左下角的值BFS的经典变体5.1 题目解读与两种思路找树左下角的值Find Bottom Left Tree Value要求返回二叉树最底层最左边节点的值。注意是最底层且最左边两者都要满足。如果最底层只有一个节点那它就是答案如果最底层有多个节点答案是这一层最左边的那个。这题有两种主流解法BFS层序遍历和DFS深度优先。我第一次想到的是BFS因为层序天然一层一层扫描记录每一层的第一个节点值扫描完整棵树后这个值自然就是最后一层的最左值。5.2 最直观的层序遍历记录每层第一个节点class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* que; que.push(root); int result root-val; while (!que.empty()) { int size que.size(); for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); if (i 0) { result node-val; } if (node-left) que.push(node-left); if (node-right) que.push(node-right); } } return result; } };这个版本的思路是用size控制每一层的节点数i 0表示该层第一个节点。每处理完一层result就被更新成当前层的最左值。当队列为空时最后一次更新的result就是最底层最左值。这个写法很直观不会有任何歧义适合作为基础版本。5.3 从右往左入队一个更简洁的经典技巧如果你希望代码更短一点有一个经典技巧BFS时先把右孩子入队再把左孩子入队那么最后一个出队的节点一定是最底层最左边的节点。代码是这样的class Solution { public: int findBottomLeftValue(TreeNode* root) { queueTreeNode* que; que.push(root); int result root-val; while (!que.empty()) { TreeNode* node que.front(); que.pop(); if (node-right) que.push(node-right); if (node-left) que.push(node-left); result node-val; } return result; } };为什么这样写是对的因为队列是先进先出。如果我们一直先推右再推左那么同一层中左边的节点会比右边的节点更晚出队。整个BFS过程中最先出队的是根节点最后出队的必然是整棵树最末尾访问到的节点。由于同一层是从右往左入队、从右往左出队也就是说同一层左边的节点比右边的晚出队所以最后出队的节点是同一层最左边的节点。又因为BFS是逐层进行的最后一层才是在队列中最后被处理的层两者一结合最后出队的节点就是最底层最左边的节点。这个技巧我第一次看的时候觉得有点绕但实测跑两次就懂了。它把记录每层第一个节点这个条件化逻辑变成了记录出队过的最后一个节点这种无条件逻辑代码更简洁但可读性稍有下降。我建议先理解5.2的基础写法再在这个基础上优化不要一上来就用技巧否则容易看不懂自己的代码。5.4 递归解法最大深度 前序遍历如果你更习惯DFS这题也可以用递归做。思路是维护一个最大深度同时前序遍历树。前序遍历天然先访问左子树再访问右子树所以第一次到达更大深度时遇到的节点一定是该层最左边的节点。class Solution { public: int maxDepth -1; int result 0; void dfs(TreeNode* node, int depth) { if (node nullptr) return; if (node-left nullptr node-right nullptr) { if (depth maxDepth) { maxDepth depth; result node-val; } return; } dfs(node-left, depth 1); dfs(node-right, depth 1); } int findBottomLeftValue(TreeNode* root) { dfs(root, 0); return result; } };这里的关键点在于判断叶子节点并且只更新第一个到达新深度的叶子。由于前序遍历是先左后右同一深度下左叶子会先被访问到。所以当遇到一个叶子节点的深度大于maxDepth时它一定是这一层第一个被访问的节点也就是最左边的节点。递归解法的空间复杂度在最坏情况下是O(n)退化成链表而BFS的空间复杂度是O(n)队列中最多存放一层的节点。两者大差不差但递归写法更符合二叉树题优先递归的思维习惯。我刷题时两种写法都会面试时如果面试官问能不能不用BFS做递归解法就是很好的备份方案。5.5 BFS和DFS的对比心得在这道题上BFS的直观性更强因为它天然逐层扫描而DFS需要额外记录深度信息来判断最左。但从通用性来说DFS在搜索一条路径的场景下更强BFS在逐层处理的场景下更强。这两种遍历框架是二叉树题的两大底座把这题的两种解法都写一遍对理解两者的边界非常有帮助。6. 打卡总结四道题背后的四个思维模型6.1 四道题的思维模型对比这四道题刷完之后我在笔记里给它们各打了一个标签用来提醒自己以后遇到同类型题目时往哪想平衡二叉树返回值设计。需要同时返回是否合法和高度时可以用一个非法值作为哨兵。对应更复杂的场景是判断二叉树是否对称、是否二叉搜索树等都可以用类似的自底向上思路。二叉树的所有路径回溯。收集从根到叶子的所有路径时值传递可以免去手动回溯但必须理解隐式回溯的原理。对应场景是打印根到指定节点的路径、求路径和等。左叶子之和条件判断的位置。判断一个节点是否是左叶子必须站在父节点的角度看。对应场景是求二叉树的所有叶子节点、求右叶子之和等。找树左下角的值遍历顺序的变化。BFS从右往左入队的变形让最左这个条件自然满足。对应场景是找最右叶子、找最靠近某个值的节点等。我把这四类问题放到一张表里题目核心考点主要解法关键易错点平衡二叉树递归返回值设计自底向上 -1哨兵只判断根节点高度差二叉树的所有路径回溯前序遍历 值传递忘记叶子节点判断左叶子之和父子关系判断后序遍历从自身角度判断左叶子找树左下角的值遍历顺序与技巧BFS从右往左入队混淆最底层与最左6.2 我的刷题心得与建议这四道题刷新完我觉得最值得反复练习的是平衡二叉树和二叉树的所有路径。前者训练递归返回值的设计能力后者训练回溯的状态感知能力。这两个能力是二叉树递归题目的两个关键支点很多更复杂的题目都是从这两个支点延伸出来的。我个人的习惯是每道题先自己用底纸画一遍示例树的递归过程标出每个入口和出口的高度值或路径字符串再去看代码。这样能直观地看到-1是怎么向上传播的路径字符串是怎么在递归返回后恢复的。画完一遍之后很多为什么就变得不用背了。另外有一点经验可以分享给你刷题打卡这件事重点不是每天刷多少题而是每道题之后有没有留下属于自己的复盘。哪怕只有三行笔记过两周再翻出来看都能快速唤醒记忆。这四道题我建议你按顺序刷先做平衡二叉树理解返回值设计再做二叉树的所有路径理解回溯接着做左叶子之和体会判断条件的位置最后做找树左下角的值感受遍历顺序带来的简化。按这个顺序递进思维链路是连贯的不会觉得每道题都是孤立的。最后说一个很多人容易忽略的小点这些题在LeetCode上都有官方题解但官方题解往往只给最优思路不会告诉你第一次写容易踩什么坑。刷题的过程中把自己错误的版本保存下来对比正确版本比单纯抄一遍标准答案有用得多。我就是习惯把每次的报错用例和错误代码存进注释里这样每次提交前扫一眼能少踩很多重复的坑。
