二叉树中存在路径和为targetSum的路径吗？

“路径总和”是一道典型的二叉树遍历问题，主要考察的是递归算法的应用。 在二叉树中寻找路径总和的问题，我们可以使用深度优先搜索（DFS）或者广度优先搜索（BFS）来解决。这里提供的参考答案使用了DFS中的递归方法。以下是详细的解释： ### 题目描述： 给定一棵二叉树的根节点`root`和一个整数`targetSum`，我们需要找出从根节点到叶子节点的路径，使得这条路径上的所有节点值之和等于`targetSum`。叶子节点是没有任何子节点的节点。 ### 示例分析： 1. 示例1：输入的二叉树结构如下，目标和为22。 ``` 5 / \ 4 8 / \ \ 11 4 7 / \ 2 1 ``` 从根节点5出发，存在一条路径`5 -> 4 -> 13 -> 1`，其路径和为22，因此输出为true。 2. 示例2：输入的二叉树结构如下，目标和为5。 ``` 1 \ 2 / 3 ``` 不存在从根节点1到叶子节点的路径和为5，所以输出为false。 3. 示例3：输入的二叉树结构如下，目标和为0。 ``` 1 \ 2 ``` 同样不存在满足条件的路径，输出为false。 ### 参考答案解析： ```cpp class Solution { public: bool hasPathSum(TreeNode* root, int sum) { if (root == nullptr) { return false; } if (root->left == nullptr && root->right == nullptr) { return sum == root->val; } return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val); } }; ``` 这段代码定义了一个名为`Solution`的类，其中有一个成员函数`hasPathSum`。这个函数接受两个参数，一个是当前遍历到的节点`root`，另一个是剩余的目标和`sum`。 - 如果`root`为空，说明已经遍历完所有节点，返回false。 - 如果`root`是一个叶子节点（即没有左右子节点），则检查当前节点的值是否等于剩余的目标和，如果是则返回true，否则返回false。 - 对于非叶子节点，分别递归地检查左子树和右子树。如果在左子树或右子树中找到满足条件的路径（即`hasPathSum`返回true），则返回true。否则，继续遍历。 这个递归解决方案的时间复杂度是O(N)，因为每个节点只被访问一次，N是二叉树的节点数量。空间复杂度是O(H)，H是二叉树的高度，这是由于递归调用栈的深度。 这是一个经典的二叉树遍历问题，通过递归方法可以有效地解决。理解并掌握这种问题对于解决其他涉及二叉树路径和的问题非常有帮助。