小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

Leetcode题目解析(191022)

2019年10月22日 715点热度 0人点赞 0条评论

Leetcode 112:路径总和

题目描述

给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明: 叶子节点是指没有子节点的节点。

示例

给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

代码实现

bool hasPathSum(TreeNode* root, int sum) {
    if (root == nullptr)
        return false;
    if ((root->left == nullptr) && (root->right == nullptr) && (root->val == sum))
        return true;
    int newsum = sum - root->val;
    return hasPathSum(root->left,newsum) || hasPathSum(root->right, newsum);

}

代码性能

执行用时:12ms(击败93.51%的C++用户)
内存消耗:19.8MB(击败50.80%的C++用户)

Leetcode 113:路径总和II

题目描述

给定一个二叉树和一个目标和,找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。

示例

给定如下二叉树,以及目标和 sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

返回:

[
[5,4,11,2],
[5,8,4,5]
]

代码实现

void hasPathSum(TreeNode* root, int sum, vector<vector<int>>& result, vector<int>& temp) {
    sum -= root->val;
    temp.push_back(root->val);
    if (sum == 0 && (root->left == nullptr) && (root->right == nullptr))
    {
        result.push_back(temp);
        return;
    }
    if (root->left)
    {
        hasPathSum(root->left, sum, result, temp);
        temp.pop_back();
    }
    if (root->right)
    {
        hasPathSum(root->right, sum, result, temp);
        temp.pop_back();
    }
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
    vector<vector<int>>result;
    if (root == nullptr)
        return result;
    vector<int>temp;
    hasPathSum(root, sum, result, temp);
    return result;
}

代码性能

执行用时:12ms(击败98.02%的C++用户)
内存消耗:19.7MB(击败88.70%的C++用户)

Leetcode 437:路径总和III

题目描述

给定一个二叉树,它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

二叉树不超过1000个节点,且节点数值范围是 [-1000000,1000000] 的整数。

示例

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

  10
 /  \
5   -3

/ \ \
3 2 11
/ \ \
3 -2 1

返回 3。和等于 8 的路径有:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

代码实现

int psum(TreeNode* root, int sum)
{
    if (root == nullptr)
        return 0;
    int res = 0;
    if (root->val == sum)
        res += 1;
    res += psum(root->left, sum - root->val);
    res += psum(root->right, sum - root->val);
    return res;
}
int pathSum(TreeNode* root, int sum) {
    if (root == nullptr)
        return 0;
    return psum(root, sum) + pathSum(root->left, sum) + pathSum(root->right, sum);
}

代码性能

时间复杂度
O(n),n为树的节点个数;
空间复杂度
O(h),h为树的高度;

执行用时:40ms(击败56.55%的C++用户)
内存消耗:14.5MB(击败89.02%的C++用户)

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年10月22日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
欢迎大家学习由昆士兰大学提供的热带海岸线生态系统课程! 奥赛·回忆 张玉帅中考成绩揭晓后的想法 山东省关于2014年中小学假期安排有关工作的通知 吴恩达深度学习课程 DeepLearning.ai 编程作业(1-4)Part.2 [leetcode]Same Tree
标签聚合
学习 鸟哥的linux私房菜 生活 高中 算法 python学习 Python Java linux leetcode
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号