剑指offer——JZ82 二叉树中和为某一值的路径（一） 解题思路与具体代码【C++】

一、题目描述与要求

二叉树中和为某一值的路径(一)_牛客题霸_牛客网 (nowcoder.com)

题目描述

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n
例如：
给出如下的二叉树，sum=22，

返回true，因为存在一条路径 5→4→11→2的节点值之和为 22

数据范围：

1.树上的节点数满足 0≤n≤10000

2.每 个节点的值都满足 ∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度O(n)

进阶：空间复杂度 O(树的高度)，时间复杂度 O(n)

示例

示例1：

输入：{5,4,8,1,11,#,9,#,#,2,7},22

返回值：true

示例2：

输入：{1,2},0

返回值：false

示例3：

输入：{1,2},3

返回值：true

示例4：

输入：{},0

返回值：false

---

二、解题思路

根据题目描述，我们需要判断这个二叉树是否存在父节点到叶子结点的路径的和等于sum，很明显我们需要对这个二叉树进行遍历，且路径定义为从树的根结点开始往下一直到叶子结点所经过的结点。因而我们需要从根结点开始逐层往下寻找，并且判断是否存在路径能够使它们的和等于sum。

比起我们去定义一个变量来计算路径之和与sum比较，这样经常需要更新，容易搞混，所以我们不如直接在访问完每个结点需要进入到下一层的时候，直接将sum减去当前结点的值，这样一直到叶子结点，只要此时sum减去叶子结点的值等于0，那么就说明路径存在，即可返回true即可。

我们可以采用递归的思想，依次访问每个结点，当然首先要判断结点是否为空，空则直接返回false，然后判断当前结点是否是叶子结点，是的话则判断sum-当前结点的值是否等于0，都满足的话代表路径存在，返回true，不满足的话就继续访问当前结点的左右子节点继续进行判断，一直到遍历完整棵树，最后返回结果即可。

---

三、具体代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @param sum int整型 
     * @return bool布尔型
     */
    bool hasPathSum(TreeNode* root, int sum) {
        //空结点找不到路径
        if(root==nullptr)  return false;
        //当访问到叶子节点并且sum此时为0 则代表找到了路径
        if(root->left==nullptr&&root->right==nullptr&&sum-root->val==0)
             return true;
        //递归访问子节点 同时将sum-当前结点的值
        return hasPathSum(root->left,sum-root->val)||hasPathSum(root->right, sum-root->val);
    }
};