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

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

function hasPathSum_1(root: TreeNode | null, targetSum: number): boolean {
  // 边界条件：空树直接返回 false（没有任何路径）
  if (!root) return false;
  
  // 栈元素：[当前节点，根到当前节点的路径和]
  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;
    
    // 核心判断：当前是叶子节点 + 路径和等于目标和 → 找到路径，返回 true
    if (!node.left && !node.right && sum === targetSum) return true;
    
    // 左子节点存在，压入栈，路径和更新为「当前和 + 左子节点值」
    if (node.left) stack.push([node.left, sum + node.left.val]);
    
    // 右子节点存在，压入栈，路径和更新为「当前和 + 右子节点值」
    if (node.right) stack.push([node.right, sum + node.right.val]);
  }
  
  // 遍历完所有路径，均不匹配，返回 false
  return false;
}

迭代解法优化点

• 移除冗余判断：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」，直到递归到叶子节点，直接判断节点值是否等于剩余目标和。

function hasPathSum_2(root: TreeNode | null, targetSum: number): boolean {
  // 递归终止条件 1：空节点（路径中断，没有可行路径）
  if (!root) return false;
  
  // 递归终止条件 2：当前节点是叶子节点 → 判断剩余目标和是否等于当前节点值
  if (!root.left && !root.right) {
    return root.val === targetSum;
  }
  
  // 递归逻辑：遍历左、右子树，目标和减去当前节点值（相当于累计路径和）
  // 只要左子树或右子树有一条路径匹配，就返回 true
  return hasPathSum_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 遍历 + 路径和记录/目标和递减」的思路。两种解法没有绝对的优劣，关键是理解其逻辑，根据场景选择合适的实现方式。