174.二叉树：路径总和（力扣）

代码解决

/*** 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 {
private:// 递归遍历二叉树，检查是否存在路径使得路径和等于countbool traversal(TreeNode* cur, int count) {// 如果当前节点是叶子节点并且计数为0，表示找到一条符合条件的路径if (!cur->left && !cur->right && count == 0) return true;// 如果当前节点是叶子节点但计数不为0，返回falseif (!cur->left && !cur->right) return false;// 递归处理左子树if (cur->left) {count -= cur->left->val; // 递归前，减少计数值if (traversal(cur->left, count)) return true; // 如果找到符合条件的路径，直接返回truecount += cur->left->val; // 回溯时，恢复计数值}// 递归处理右子树if (cur->right) {count -= cur->right->val; // 递归前，减少计数值if (traversal(cur->right, count)) return true; // 如果找到符合条件的路径，直接返回truecount += cur->right->val; // 回溯时，恢复计数值}// 如果左、右子树都没有找到符合条件的路径，返回falsereturn false;}public:// 主函数，检查从根节点到叶子节点的路径和是否等于sumbool hasPathSum(TreeNode* root, int sum) {if (root == NULL) return false; // 如果根节点为空，返回falsereturn traversal(root, sum - root->val); // 从根节点开始递归，初始计数为sum减去根节点值}
};

• Solution 类：

  • 包含一个私有方法 traversal 和一个公有方法 hasPathSum。

• traversal 方法：

  • 递归遍历二叉树，检查是否存在路径使得路径和等于 count。
  • 如果当前节点是叶子节点并且 count 为0，返回 true。
  • 如果当前节点是叶子节点但 count 不为0，返回 false。
  • 递归处理左子树和右子树，递归前减少计数值，回溯时恢复计数值。

• hasPathSum 方法：

  • 主函数，检查从根节点到叶子节点的路径和是否等于 sum。
  • 如果根节点为空，返回 false。
  • 从根节点开始递归，初始计数为 sum 减去根节点值。

方法二 

/*** 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 sum) {// 如果根节点为空，返回 falseif (root == nullptr) return false;// 如果当前节点是叶子节点，且路径和等于 sum，返回 trueif (root->left == nullptr && root->right == nullptr && sum == root->val) return true;// 递归检查左子树或右子树是否存在满足条件的路径return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);}
};

这里简要解释一下代码的工作流程：

1. 首先判断根节点是否为空，如果为空，返回 false。
2. 检查当前节点是否是叶子节点，并且其值是否等于路径上的总和 sum，如果是，返回 true。
3. 递归地检查左子树 hasPathSum(root->left, sum - root->val) 和右子树 hasPathSum(root->right, sum - root->val)，看是否存在满足条件的路径。
4. 如果左右子树中任一棵存在满足条件的路径，则返回 true；否则返回 false。

这个算法的时间复杂度是 O(n)，因为每个节点都会被访问一次，其中 n 是树中节点的数量。空间复杂度也是 O(n)，因为需要存储递归调用的栈。