10、路径总和

哈喽，大家好，我是厨子，今天给大家分享一下路径总和这道题目

https://leetcode.cn/problems/path-sum/description/

题目描述

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum。判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和 targetSum。

如果存在，返回 true；否则，返回 false。

叶子节点是指没有子节点的节点。

示例 1:

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶子节点路径如图所示。
      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1

路径: 5 -> 4 -> 11 -> 2
路径和: 5 + 4 + 11 + 2 = 22 ✓

示例 2:

输入：root = [1,2,3], targetSum = 5
输出：false
解释：树中存在两条根节点到叶子节点的路径：
(1 --> 2): 和为 3
(1 --> 3): 和为 4
不存在 sum = 5 的根节点到叶子节点的路径。
    1
   / \
  2   3

示例 3:

输入：root = [], targetSum = 0
输出：false
解释：由于树是空的，所以不存在根节点到叶子节点的路径。

约束条件:

• 树中节点的数目在范围 [0, 5000] 内
• -1000 <= Node.val <= 1000
• -1000 <= targetSum <= 1000

什么是根到叶子的路径？

路径的概念

什么是路径？
从根节点出发，沿着父子连接，一直走到叶子节点的完整路径

什么是叶子节点？
没有左右子节点的节点（left == null && right == null）

注意：只有叶子节点才算终点！

常见误区

错误理解：
      5
     / \
    4   8
   /
  11

路径 5 -> 4 (sum = 9) ✗ 错误！
→ 节点4不是叶子节点，它还有子节点11


正确理解：
      5
     / \
    4   8
   /
  11

路径 5 -> 4 -> 11 (sum = 20) ✓ 正确！
→ 节点11是叶子节点（没有子节点）

路径示例

示例树：
      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1

所有从根到叶子的路径：
1. 5 -> 4 -> 11 -> 7  (sum = 27)
2. 5 -> 4 -> 11 -> 2  (sum = 22) ← 如果 targetSum = 22，返回 true
3. 5 -> 8 -> 13       (sum = 26)
4. 5 -> 8 -> 4 -> 1   (sum = 18)

关键点：
- 必须从根节点开始
- 必须到叶子节点结束
- 路径上的节点不能重复
- 只要有一条路径满足条件就返回 true

解题思路

方法一：递归（DFS）⭐

核心思想

使用深度优先搜索，从根节点开始递归：

1. 每次递归时，用 targetSum 减去当前节点的值
2. 到达叶子节点时，检查剩余的 targetSum 是否为 0
3. 非叶子节点：递归检查左子树或右子树是否存在满足条件的路径

详细图解示例

以示例1为例：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 / \       \
7   2       1


执行过程：

步骤1: hasPathSum(5, 22)
  不是叶子节点
  递归左子树: hasPathSum(4, 22-5=17)
  递归右子树: hasPathSum(8, 22-5=17)

步骤2: hasPathSum(4, 17)  [处理左子树]
  不是叶子节点
  递归左子树: hasPathSum(11, 17-4=13)
  递归右子树: hasPathSum(null, 17-4=13) → false

步骤3: hasPathSum(11, 13)  [处理节点11]
  不是叶子节点
  递归左子树: hasPathSum(7, 13-11=2)
  递归右子树: hasPathSum(2, 13-11=2)

步骤4: hasPathSum(7, 2)  [处理节点7]
  是叶子节点
  7 ≠ 2，返回 false

步骤5: hasPathSum(2, 2)  [处理节点2]
  是叶子节点
  2 == 2，返回 true ✓

找到路径：5 -> 4 -> 11 -> 2 (sum = 22)

代码实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        // 空节点，返回 false
        if (root == nullptr) {
            return false;
        }

        // 叶子节点，检查是否等于 targetSum
        if (root->left == nullptr && root->right == nullptr) {
            return root->val == targetSum;
        }

        // 递归情况: 检查左子树或右子树是否存在路径
        int remainingSum = targetSum - root->val;
        return hasPathSum(root->left, remainingSum) ||
               hasPathSum(root->right, remainingSum);
    }
};

时间复杂度: O(n)，其中 n 是树中节点的数量。最坏情况下需要遍历所有节点。

空间复杂度: O(h)，其中 h 是树的高度。递归调用栈的深度等于树的高度。

• 最坏情况（链式树）：O(n)
• 最好情况（平衡树）：O(log n)