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

WZEARW

发布于 2018-04-11 16:28:53

6930

发布于 2018-04-11 16:28:53

文章被收录于专栏：专知

关关的刷题日记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）。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2017-12-07，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树