前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【关关的刷题日记58】Leetcode 112 Path Sum

【关关的刷题日记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:我们可以计算出当前路径的和,判断是否与给定和相等,只要有一条路径相等即可。需要一个额外的参数来保存当前路径的和,因此我们再额外调用一个递归函数。如果要是当前节点是叶子节点,判断一下当前和给定和是否相等;如果当前节点不是叶子节点,那么分别判断它的左右子树路径中是否有路径满足条件,判断左右子树是否有路径满足条件的过程和判断该树是否有路径满足条件的过程是一样的,采用递归的解法。

代码语言:javascript
复制
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:看了别人的答案,采用逆向思维,并不是把节点值一点点加起来求当前和,判断是否与给定和相等。而是用给定和一点点减去节点值求当前和,直到叶节点的时候,判断叶节点值是否与当前和相等。这种方法不太好想,但是不需要设置一个额外参数,写起来很简洁。

代码语言:javascript
复制
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 删除

本文分享自 专知 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档