当前位置:网站首页>LeetCode:124. 二叉树中的最大路径和
LeetCode:124. 二叉树中的最大路径和
2022-07-06 08:44:00 【Bertil】
路径 被定义为一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。
路径和 是路径中各节点值的总和。
给你一个二叉树的根节点 root ,返回其 最大路径和 。
示例 1:
输入:root = [1,2,3]
输出:6
解释:最优路径是 2 -> 1 -> 3 ,路径和为 2 + 1 + 3 = 6
示例 2:
输入:root = [-10,9,20,null,null,15,7]
输出:42
解释:最优路径是 15 -> 20 -> 7 ,路径和为 15 + 20 + 7 = 42
提示:
- 树中节点数目范围是 [1, 3 * 10^4]
- -1000 <= Node.val <= 1000
解题思路
1.首先遍历左右子树的深度,当前节点往下走的最大值分三种情况:
- 往左走:当前节点+L(左子树的最大深度)
- 往右走:当前节点+R(右子树的最大深度)
- 不走:当前节点如果为负值,直接返回0
2.然后定义最大路径和ans为根节点+左子树+右子树的深度最大值
3.最后,递归完成后直接返回最大路径和ans即可
代码
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } */
/** * @param {TreeNode} root * @return {number} */
var maxPathSum = function(root) {
let ans = -9999;
dfs(root);
return ans;
// 从当前节点往下走
function dfs(root) {
if(!root) return 0;
// 遍历左子树的深度
let left = dfs(root.left);
// 遍历右子树的深度
let right = dfs(root.right);
// 更新路径的最大值
ans = Math.max(ans, root.val + left + right);
// 返回从当前节点往下走的最大值
return Math.max(0, Math.max(left, right) + root.val);
}
};
边栏推荐
- sublime text中conda环境中plt.show无法弹出显示图片的问题
- Hutool gracefully parses URL links and obtains parameters
- JVM 快速入门
- 【嵌入式】使用JLINK RTT打印log
- China high purity silver nitrate Market Research and investment strategy report (2022 Edition)
- Using pkgbuild:: find in R language_ Rtools check whether rtools is available and use sys The which function checks whether make exists, installs it if not, and binds R and rtools with the writelines
- 704 binary search
- @JsonBackReference和@JsonManagedReference(解决对象中存在双向引用导致的无限递归)
- 深度剖析C语言数据在内存中的存储
- TP-LINK enterprise router PPTP configuration
猜你喜欢
广州推进儿童友好城市建设,将探索学校周边200米设安全区域
Sublime text using ctrl+b to run another program without closing other runs
可变长参数
Deep analysis of C language pointer
UnsupportedOperationException异常
ESP8266-RTOS物联网开发
Unified ordering background interface product description Chinese garbled
TP-LINK enterprise router PPTP configuration
ROS编译 调用第三方动态库(xxx.so)
Deep anatomy of C language -- C language keywords
随机推荐
Leetcode question brushing (5.31) string
logback1.3. X configuration details and Practice
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
Mobile phones and computers on the same LAN access each other, IIS settings
win10系统中的截图,win+prtSc保存位置
UnsupportedOperationException异常
sublime text的编写程序时的Tab和空格缩进问题
Visual implementation and inspection of visdom
Detailed explanation of heap sorting
TDengine 社区问题双周精选 | 第三期
JS pure function
TCP/IP协议
C语言深度解剖——C语言关键字
Sublime text in CONDA environment plt Show cannot pop up the problem of displaying pictures
【嵌入式】Cortex M4F DSP库
Beijing invitation media
MySQL learning record 11jdbcstatement object, SQL injection problem and Preparedstatement object
POI add write excel file
Research Report on Market Research and investment strategy of microcrystalline graphite materials in China (2022 Edition)
Pointer advanced --- pointer array, array pointer