C++算法练习-day37——112.路径总和

题目来源：. - 力扣（LeetCode）

题目思路分析

题目要求判断一棵二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上所有节点的值相加等于一个给定的目标和（targetSum）。为了解决这个问题，我们可以使用深度优先搜索（DFS）策略。从根节点开始，递归地向下遍历树，每次将当前节点的值从目标和中减去，并检查是否到达叶子节点且目标和恰好减到0。如果在某个分支上找到了符合条件的路径，则返回true；如果遍历完所有可能的路径都没有找到符合条件的路径，则返回false。

代码:

#include <iostream>  
  
// 二叉树节点的定义  
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) {  
            return false;  
        }  
          
        // 从目标和中减去当前节点的值  
        targetSum -= root->val;  
          
        // 如果当前节点是叶子节点（没有左右子节点），则检查目标和是否减到0  
        if (!root->left && !root->right) {  
            return targetSum == 0;  
        }  
          
        // 递归地在左子树和右子树中查找路径  
        // 如果左子树或右子树中存在符合条件的路径，则返回true  
        return hasPathSum(root->left, targetSum) || hasPathSum(root->right, targetSum);  
    }  
};  
  
// 示例用法  
int main() {  
    // 构造一棵二叉树  
    TreeNode* root = new TreeNode(5);  
    root->left = new TreeNode(4);  
    root->right = new TreeNode(8);  
    root->left->left = new TreeNode(11);  
    root->right->left = new TreeNode(13);  
    root->right->right = new TreeNode(4);  
    root->left->left->left = new TreeNode(7);  
    root->left->left->right = new TreeNode(2);  
    root->right->right->right = new TreeNode(1);  
      
    Solution solution;  
    int targetSum = 22;  
    bool result = solution.hasPathSum(root, targetSum);  
      
    // 输出结果  
    std::cout << (result ? "存在路径" : "不存在路径") << std::endl;  
      
    // 释放内存（这里省略了详细的内存释放代码，实际使用时需要注意避免内存泄漏）  
      
    return 0;  
}

注释详解

1. 检查根节点是否为空：如果根节点为空，则直接返回false，因为不存在任何路径。
2. 更新目标和：将当前节点的值从目标和中减去，以便在递归过程中检查剩余路径上的节点值之和是否等于0。
3. 检查叶子节点：如果当前节点是叶子节点（即没有左右子节点），则检查目标和是否减到0。如果是，则返回true，表示找到了一条符合条件的路径。
4. 递归查找：如果当前节点不是叶子节点，则递归地在左子树和右子树中查找是否存在符合条件的路径。使用逻辑或操作符||连接两个递归调用，因为只要左子树或右子树中存在符合条件的路径，整个函数就应该返回true。

知识点摘要

1. 深度优先搜索（DFS）：一种图搜索算法，用于遍历或搜索图形数据结构中的节点。DFS通过递归或栈来实现，沿着树的深度遍历节点，直到达到叶子节点或遍历完所有可能的分支。
2. 二叉树：一种树形数据结构，其中每个节点最多有两个子节点，称为左子节点和右子节点。
3. 递归：一种在函数内部调用自身的方法，通常用于解决可以分解为相似子问题的问题。

通过上述分析，我们了解了如何使用深度优先搜索（DFS）来判断一棵二叉树中是否存在一条从根节点到叶子节点的路径，使得路径上所有节点的值相加等于一个给定的目标和。DFS通过递归地遍历树的所有可能路径，并检查每条路径上节点值之和是否等于目标和，从而找到符合条件的路径。这种方法是直观且有效的，适用于解决类似的问题。在实际编程中，我们还需要注意内存管理，避免内存泄漏等问题。