LeetCode实战：二叉树中的最大路径和
背景
- 为什么你要加入一个技术团队？
- 如何加入 LSGO 软件技术团队？
- 我是如何组织“算法刻意练习活动”的？
- 为什么要求团队的学生们写技术Blog
题目英文
Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example 1:
Input: [1,2,3]1/ \2 3Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]-10/ \9 20/ \15 7Output: 42
题目中文
给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
示例 1:
输入: [1,2,3]1/ \2 3输出: 6
示例 2:
输入: [-10,9,20,null,null,15,7]-10/ \9 20/ \15 7输出: 42
算法实现
8/ \-3 7/ \
1 4
考虑左子树 -3 的路径的时候，我们有左子树 1 和右子树 4 的选择，但我们不能同时选择。
如果同时选了，路径就是 … -> 1 -> -3 -> 4 就无法通过根节点 8 了。
所以我们只能去求左子树能返回的最大值，右子树能返回的最大值，选一个较大的。
/*** Definition for a binary tree node.* public class TreeNode {* public int val;* public TreeNode left;* public TreeNode right;* public TreeNode(int x) { val = x; }* }*/
public class Solution
{private int _max = int.MinValue;public int MaxPathSum(TreeNode root){MaxPath(root);return _max;}private int MaxPath(TreeNode current){if (current == null)return 0;int left = Math.Max(MaxPath(current.left), 0);int right = Math.Max(MaxPath(current.right), 0);_max = Math.Max(_max, current.val + left + right);return current.val + Math.Max(left, right);}
}
实验结果
- 状态：通过
- 93 / 93 个通过测试用例
- 执行用时: 152 ms, 在所有 C# 提交中击败了 86.96% 的用户
- 内存消耗: 29.7 MB, 在所有 C# 提交中击败了 37.50% 的用户
相关图文
1. “数组”类算法
- LeetCode实战：三数之和
- LeetCode实战：最接近的三数之和
- LeetCode实战：求众数
- LeetCode实战：缺失的第一个正数
- LeetCode实战：快乐数
- LeetCode实战：寻找两个有序数组的中位数
- LeetCode实战：盛最多水的容器
- LeetCode实战：删除排序数组中的重复项
- LeetCode实战：搜索旋转排序数组
- LeetCode实战：螺旋矩阵
- LeetCode实战：螺旋矩阵 II
2. “链表”类算法
- LeetCode实战：两数相加
- LeetCode实战：删除链表的倒数第N个节点
- LeetCode实战：合并两个有序链表
- LeetCode实战：合并K个排序链表
- LeetCode实战：两两交换链表中的节点
- LeetCode实战：旋转链表
- LeetCode实战：环形链表
3. “栈”类算法
- LeetCode实战：有效的括号
- LeetCode实战：最长有效括号
- LeetCode实战：逆波兰表达式求值
4. “队列”类算法
- LeetCode实战：设计循环双端队列
- LeetCode实战：滑动窗口最大值
- LeetCode实战：整数反转
- LeetCode实战：字符串转换整数 (atoi)
5. “递归”类算法
- LeetCode实战：爬楼梯
6. “字符串”类算法
- LeetCode实战：反转字符串
- LeetCode实战：翻转字符串里的单词
- LeetCode实战：最长公共前缀
- LeetCode实战：字符串相加
- LeetCode实战：字符串相乘
7. “树”类算法
- LeetCode实战：相同的树
- LeetCode实战：对称二叉树
- LeetCode实战：二叉树的最大深度
- LeetCode实战：将有序数组转换为二叉搜索树
8. “哈希”类算法
- LeetCode实战：两数之和
9. “搜索”类算法
- LeetCode实战：搜索二维矩阵
- LeetCode实战：子集
10. “动态规划”类算法
- LeetCode实战：最长回文子串
- LeetCode实战：最大子序和
- LeetCode实战：不同路径
11. “回溯”类算法
- LeetCode实战：全排列
12. “数值分析”类算法
- LeetCode实战：回文数
- LeetCode实战：x 的平方根
相关文章：
为Visual Studio添加配色方案
看到网上有一些教程，他们的代码截图，不是VS默认的白底黑字，觉得挺好看，就也把自己的VS鼓捣了一把： 使用的是现成的配色方案，试了好几种，就觉得这个看着舒服son-of-obsidian.vssettings 你可以去…
黑色星期五阿里云向海淘输出双11技术
本文讲的是"黑色星期五"阿里云向海淘输出双11技术【IT168资讯】11月27日零点，“黑色星期五”正式到来，虽然远在中国的消费者无法参与海外的实体抢购，但电商平台却给了他们从地球另一端参与“大抢购”的机会。随着近年海淘市场的不断…
专业的java培训机构是否靠谱，对比一下就知道了!
java在IT行业的火热是有目共睹的，所以市面上有很多机构都抓住了这点，开设了java培训课程，想要找到一个适合自己的java培训机构，多进行对比就知道了! 专业的java培训机构是否靠谱，对比一下就知道了!专业的Java培训机构靠…
LeetCode实战：环形链表 II
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a linked list, return the node where the cycle begins. If there is no cycle, re…
.NET中使用OracleHelper
以前一直使用MSSQL,数据库操作类也是自己写的.现在项目使用Oracle,数据库操作类用的是MICROSOFT的DAAB中的OracleHelper.实际使用过程中,发现坛内少有此方面使用经验的贴子,故在这里把我使用中的一点经验用几个例子说明一下,希望起到抛砖引玉的作用. 查询数据方面: 1.简单的SQL…
新勒索软件DynA-Crypt不仅要加密你的文件，而且窃取并删除它们
本文讲的是新勒索软件DynA-Crypt不仅要加密你的文件，而且窃取并删除它们，一个名为DynA-Crypt的新勒索软件被GData公司的恶意软件分析师Karsten Hahn发现，DynA-Crypt不仅能加密你的数据，而且试图从受害者的计算机窃取大量信息。虽然…
【Postman】6 Postman 发送post请求-Json格式
一、post请求说明 使用postman发送一个post请求，在上文中测试流程中提到的4个要素：URL、请求方式、请求头部信息及body数据。 body中设置的请求参数，常见的有如下三种： 1、x-www-from-urlencoded格式 2、form data格式 3、Json格式…
LeetCode实战：最小栈
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Design a stack that supports push, pop, top, and retrieving the minimum element in co…
配置国内 Docker Registry Mirror
由于国内特殊的网络环境，往往我们从Docker Hub中拉取镜像并不能成功，而且速度特别慢。 那么我们可以给Docker配置一个国内的registry mirror，当我们需要的镜像在mirror中则直接返回，如果没有则从Docker Hub中拉取。是否使用regist…
Java培训深度学习都要学什么
java的知识点有很多，如果是有java基础的同学，进行深度学习是非常有必要的，比较职场技能更新迭代非常的快，那么java培训深度学习都要学什么呢?来看看下面的详细介绍。 Java培训深度学习都要学什么? Java深度学习要掌握两点&#…
LeetCode实战：相交链表
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Write a program to find the node at which the intersection of two singly linked lists…
# 30 天精通 RxJS (01)：认识 RxJS
RxJS 是笔者认为未来几年内会非常红的 Library，RxJS 提供了一套完整的非同步解决方案，让我们在面对各种非同步行为，不管是 Event, AJAX, 还是 Animation 等，我们都可以使用相同的 API (Application Programming Interface) 做开发…
ThickBox 3.1参数详解(转)
前几天写了一篇关于ThickBox 3.1的文章：今天在使用这个东西的时候发现里面有许多参数没有详细解释，今天抽空整理出来，现和大家分享一下：先说几个参数：class"thickbox" 调用特效；height 打开页面的…
最新Java培训-NIO实战教程
Java NIO(New IO)是一个可以替代标准Java IO API的IO API(从Java 1.4开始)，Java NIO提供了与标准IO不同的IO工作方式。NIO可以理解为非阻塞IO,传统的IO的read和write只能阻塞执行，线程在读写IO期间不能干其他事情，比如调用socket.read()时&am…
获取执行SQL语句的返回结果
最近遇到的问题，在存储过程中需要拼接动态SQL语句，用变量保存，可直接使用EXECUTE SP_EXECUTESQL是不能获取想要的结果的 于是经过baidu了一番后，找到了解决的办法 declare coun int,sql nvarchar(2000)setsqlselect councount(*) …
Word文档使用密码加密
Word文档使用密码加密 方法如下： 文件-->信息-->保护文档-->用密码进行加密-->设置密码
LeetCode实战：反转链表
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Ou…
【UI设计培训】字体设计-偏旁部首变形
UI设计培训中字体设计也是非常重要的一节课，字体在UI设计岗位中可以说用到的频率是非常高的，是设计师必须学会并且要有娴熟运用的一项必备技能，在进行汉字设计的时候，可以把汉字拆分成几个偏旁部首的形式进行设计，这样…
【转帖】如何通过 javascript 访问 GridView/DataGrid 选中 CheckBox 行各列的值
功能需求1, 单击 checkbox 返回当前行值2, 外部按钮获取所有选择行的值实现说明参见主要代码，代码为自说明式。原文地址：http://www.cnblogs.com/Jinglecat/archive/2007/07/15/818967.html主要代码 <asp:GridView ID"GridView1" runat&q…
LeetCode实战：删除链表中的节点
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Write a function to delete a node (except the tail) in a singly linked list, given on…
Facebook将React的许可改为MIT
Facebook决定将React原先的BSDPatents许可改为MIT，这样其他公司就可以将React包含在Apache基金会的项目当中，并消除与开源社区之间关系的不确定性。\\Facebook的一位工程主管Adam Wolff声称，将会有越来越多的项目使用MIT许可代替BSDPatents&a…
Java培训进阶书籍推荐，赶快收藏起来!
最近有很多学习或者已经在工作的java技术的同学都想要更进一步的提升自己，那么阅读书籍可以给大家带来帮助，今天，小编将分享过去几年中一些最好的Java培训进阶书籍，您可以在2021年阅读这些书籍，以更好地学习Java和相关…
LeetCode实战：二叉搜索树的最近公共祖先
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given …
[转载] 杜拉拉升职记——02 单相思与性骚扰
来源：李可. 杜拉拉升职记(第三版). 西安: 陕西师范大学出版社, 2010, 5. 02 单相思与性骚扰的区别 拉拉注意到，DB所有经理办公室沿走道的这一面，都是用大块的玻璃来做间隔墙。 拉拉问海伦：“这么设计是为了美观吗？” …
走进云计算与虚拟化的底层核心
本文讲的是走进云计算与虚拟化的底层核心,2012年3月在国务院政府工作报告附录部分中，政府对云计算给出了官方的解释，体现了政府对云计算产业的高度重视和美好愿景。云计算在工作报告中是这样定义的：“云计算是基于互联网的服务的增加、使用和…
LeetCode实战：LRU缓存机制
背景 为什么你要加入一个技术团队？如何加入 LSGO 软件技术团队？我是如何组织“算法刻意练习活动”的？为什么要求团队的学生们写技术Blog 题目英文 Design and implement a data structure for Least Recently Used (LRU) cache. It should …
探索性测试，笔记二
测试十戒律： 1、你应该使用大量输入，来反复锤炼被测的应用程序 *大规模的随机测试（自动化），而且有助于理解输入和输出的关系 2、你应当贪图你的邻居的应用程序 3、你应当亲自寻找睿智的预言家 *对应的输入是否有对应的…
python 监控windows磁盘空间和备份大小
#!/usr/bin/env python # Version 3.5.2 # __auth__ 无名小妖 import os import time import sendmail import psutil import collectionsdisk_used collections.OrderedDict() cur_time time.time() # current_day cur_time - cur_time % 86400 root_dir ["D:\\bac…
如何高效学习java课程
想要快速进入到java行业，进行系统的培训和有效的学习是非常重要的，那么短时间内如何高效学习java课程呢?来看看下面小编的详细介绍吧。 如何高效学习java课程? 1. 克服自身惰性，学习环境更佳。 参加Java培训机构学习的话，…
2021年web前端发展方向有哪些
一年转瞬即逝，仅仅一年的时间，就能发生很多事情，近几年web前端行业越来越受到大家的关注，很多人都想看看2021年web前端发展方向有哪些?下面来看看小编详细的介绍。 2021年web前端发展方向有哪些? 1、TypeScript爆发增长 从2019年…