关关的刷题日记58 – Leetcode 112 Path Sum

题目

题目的意思是判断一棵二叉树跟到叶子节点的所有路径中是否有一条路径的和等于给定的和。

方法1：我们可以计算出当前路径的和，判断是否与给定和相等，只要有一条路径相等即可。需要一个额外的参数来保存当前路径的和，因此我们再额外调用一个递归函数。如果要是当前节点是叶子节点，判断一下当前和给定和是否相等；如果当前节点不是叶子节点，那么分别判断它的左右子树路径中是否有路径满足条件，判断左右子树是否有路径满足条件的过程和判断该树是否有路径满足条件的过程是一样的，采用递归的解法。

class Solution {
public:
    bool dfs(TreeNode* root, int cur, int sum)
    {
        if(!root->left && !root->right)
            return root->val+cur==sum;
        bool left=false, right=false;
        if(root->left)
            left=dfs(root->left, cur+root->val, sum);
        if(root->right)
            right=dfs(root->right,cur+root->val,sum);
        return left|| right;       
    }

    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        return dfs(root,0,sum);
    }
};

方法2：看了别人的答案，采用逆向思维，并不是把节点值一点点加起来求当前和，判断是否与给定和相等。而是用给定和一点点减去节点值求当前和，直到叶节点的时候，判断叶节点值是否与当前和相等。这种方法不太好想，但是不需要设置一个额外参数，写起来很简洁。

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==nullptr)
            return false;
        if(!root->left && !root->right && root->val==sum)
                return true;
        else
            return hasPathSum(root->left, sum-root->val) ||hasPathSum(root->right, sum-root->val);
    }
};

照顾好自己的身体，控制好自己的情绪，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。