LeetCode 112. 路径总和：两种解法详解

二叉树的路径问题算是高频考点之一，今天拆解 LeetCode 简单难度的 112. 路径总和，不仅搞懂题目核心，还会对比两种常用解法（迭代 DFS + 递归 DFS），帮助理清思路、避坑易错点，适合刚接触二叉树路径题的小伙伴入门。

一、题目解读

题目很直白，给定二叉树的根节点 root 和目标和 targetSum，判断是否存在一条从 根节点到叶子节点 的路径，这条路径上所有节点的值相加等于 targetSum。

这里有两个关键细节，一定要注意（否则容易踩坑）：

• 路径必须是「根节点 → 叶子节点」，中间不能中断，也不能是叶子节点到其他节点、非根节点到叶子节点；
• 叶子节点的定义：没有左、右子节点的节点（即 left === null 且 right === null），这是判断路径终点的核心条件。

举个简单例子：如果二叉树只有根节点，值为 5，targetSum 为 5 → 根节点就是叶子节点，返回 true；如果根节点值为 5，有一个左子节点值为 3，targetSum 为 5 → 没有到叶子节点的路径（根节点不是叶子，左子节点未判断总和），返回 false。

二、核心思路

这道题的核心是「遍历二叉树」，并记录从根节点到当前节点的路径和，当遍历到叶子节点时，判断路径和是否等于目标和。

二叉树的遍历有递归和迭代两种常用方式，对应到这道题，我们可以实现两种解法，本质都是深度优先搜索（DFS）—— 优先走一条路径到叶子，再回溯走其他路径，效率一致，但编码风格不同。

三、完整解法

先给出 TreeNode 的定义（题目已提供，此处复用，保证代码可直接运行）：

classTreeNode{ val:number left: TreeNode |null right: TreeNode |nullconstructor(val?:number, left?: TreeNode |null, right?: TreeNode |null){this.val =(val ===undefined?0: val)this.left =(left ===undefined?null: left)this.right =(right ===undefined?null: right)}}

解法一：迭代 DFS

迭代方式用「栈」存储遍历的节点，同时记录「从根节点到当前节点的路径和」，每弹出一个节点，就判断是否为叶子节点、路径和是否匹配，不匹配则继续压入其左右子节点（带更新后的路径和）。

下面是题目给出的初始代码，以及我优化后的细节说明：

functionhasPathSum_1(root: TreeNode |null, targetSum:number):boolean{// 边界条件：空树直接返回false（没有任何路径）if(!root)returnfalse;// 栈元素：[当前节点, 根到当前节点的路径和]const stack:[TreeNode,number][]=[[root, root.val]];// 栈非空，说明还有路径未遍历while(stack.length){// 弹出栈顶节点（DFS 特性：后进先出）const cur = stack.pop();// 冗余判断？其实stack.length>0时，pop()不会返回undefined，可优化if(!cur)continue;// 解构当前节点和路径和const[node, sum]:[TreeNode,number]= cur;// 核心判断：当前是叶子节点 + 路径和等于目标和 → 找到路径，返回trueif(!node.left &&!node.right && sum === targetSum)returntrue;// 左子节点存在，压入栈，路径和更新为「当前和 + 左子节点值」if(node.left) stack.push([node.left, sum + node.left.val]);// 右子节点存在，压入栈，路径和更新为「当前和 + 右子节点值」if(node.right) stack.push([node.right, sum + node.right.val]);}// 遍历完所有路径，均不匹配，返回falsereturnfalse;};

迭代解法优化点

• 移除冗余判断：while 循环条件是 stack.length（栈非空），此时 stack.pop() 一定不会返回 undefined，可改用 const [node, sum] = stack.pop()!（TypeScript 断言），省去 if (!cur) continue；
• 调整子节点压入顺序：先压右子节点，再压左子节点，保证遍历顺序是「左→右」（符合常规 DFS 习惯，不影响结果，但更易理解）；
• 变量命名语义化：将 cur、node、sum 改为 currentNode、currentSum，更直观。

解法二：递归 DFS

递归的核心是「拆分问题」：判断根节点到叶子的路径和，可拆分为「根节点的左子树是否有路径和为 targetSum - root.val」或「根节点的右子树是否有路径和为 targetSum - root.val」，直到递归到叶子节点，直接判断节点值是否等于剩余目标和。

functionhasPathSum_2(root: TreeNode |null, targetSum:number):boolean{// 递归终止条件1：空节点（路径中断，没有可行路径）if(!root)returnfalse;// 递归终止条件2：当前节点是叶子节点 → 判断剩余目标和是否等于当前节点值if(!root.left &&!root.right){return root.val === targetSum;}// 递归逻辑：遍历左、右子树，目标和减去当前节点值（相当于累计路径和）// 只要左子树或右子树有一条路径匹配，就返回truereturnhasPathSum_2(root.left, targetSum - root.val)||hasPathSum_2(root.right, targetSum - root.val);}

递归解法核心理解

很多小伙伴刚开始看递归会懵，其实可以这样想：

比如 targetSum 是 10，根节点值是 5，那么我们只需要判断「左子树是否有路径和为 5」或者「右子树是否有路径和为 5」；如果左子节点值是 3，那么继续判断「左子节点的子树是否有路径和为 2」，直到走到叶子节点，直接判断叶子节点值是否等于剩余的目标和。

这种方式不用手动记录路径和，而是通过「目标和递减」的方式间接实现，代码更简洁。

四、两种解法对比

总结：日常刷题、面试答题，优先选递归解法（代码简洁，易写易读）；如果题目明确说明树可能极深，再用迭代解法规避栈溢出问题。

五、易错点总结

• 忽略叶子节点定义：误将「只有左子节点或只有右子节点」的节点当作叶子节点，导致判断条件错误（正确条件：!node.left && !node.right）；
• 路径范围错误：误判为「任意节点到叶子节点」，忘记题目要求是「根节点到叶子节点」；
• 递归终止条件遗漏：递归时未判断空节点，导致报错（空节点没有 val 属性，会触发 TypeError）；
• 迭代时栈元素错误：只存储节点，未存储路径和，导致无法判断当前路径的总和。

六、刷题延伸

掌握这道题后，可以试试同类型的路径题，巩固 DFS 思路：

• LeetCode 113. 路径总和 II（找出所有根到叶子的路径和等于目标和的路径）；
• LeetCode 437. 路径总和 III（不限制根节点和叶子节点，任意路径和等于目标和）。

七、解题总结

112.路径总和是二叉树路径问题的入门题，核心是掌握「DFS 遍历 + 路径和记录/目标和递减」的思路。两种解法没有绝对的优劣，关键是理解其逻辑，根据场景选择合适的实现方式。