机考刷题之 2 LeetCode 112 路径总合

题目

分析

看见评论区有人总结了二叉树递归类题型的诀窍：

题目中是从根节点到叶子节点，每经过一个节点，target值就减去这个节点的val。那么在第一个模板中，当为叶子节点时，我们应该判断target值减去当前的叶子节点的val后最后是否为0，如果是，则返回true，反之为false。

如果只是中间节点，那么则需要继续递归遍历其左右子节点。

还要注意节点为空，直接返回false。

代码

/** * 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) { if(root == nullptr) return false;//如果是空节点就返回false targetSum = targetSum - root->val; if(root->left == nullptr && root->right == nullptr ){//叶子节点，判断是否满足条件（即目标值一路减下来到叶子节点时是否为0 return targetSum == 0; } return hasPathSum(root->left,targetSum) || hasPathSum(root->right,targetSum);//如果不是叶子节点，也不是空节点，就遍历左右子节点 } };

结果

关于二叉树递归，千问给出的诀窍总结：

写递归要牢记三要素：

1️⃣递归的定义（做什么）

函数hasPathSum(root, targetSum)表示：以 root 为起点，是否存在一条到叶子的路径，使得路径和等于 targetSum。

2️⃣递归的终止条件（边界）

• 如果root == null，说明走到空节点了 → 不是有效路径 → 返回false。
• 如果root是叶子（左右都为空），那么检查root.val == targetSum是否成立。

3️⃣递归的拆解（如何缩小问题）

• 当前节点不是叶子，那就把问题交给左右子树：
  • 左子树是否有一条路径和为targetSum - root.val？
  • 或者右子树是否有？
• 只要一边满足，就返回true。