【关关的刷题日记58】Leetcode 112 Path Sum- 专知

【关关的刷题日记58】Leetcode 112 Path Sum

点击上方“专知”，关注获取专业AI知识”

关关的刷题日记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);
    }};