当前位置:网站首页>LeetCode:124. Maximum path sum in binary tree
LeetCode:124. Maximum path sum in binary tree
2022-07-06 08:51:00 【Bertil】
route It is defined as a path starting from any node in the tree , Along the parent node - Child node connection , A sequence that reaches any node . The same node in a path sequence At most once . This path At least one node , And it doesn't have to go through the root node .
Path and Is the sum of the values of the nodes in the path .
Give you the root node of a binary tree root , Back to its The maximum path and .
Example 1:
Input :root = [1,2,3]
Output :6
explain : The best path is 2 -> 1 -> 3 , Path and are 2 + 1 + 3 = 6
Example 2:
Input :root = [-10,9,20,null,null,15,7]
Output :42
explain : The best path is 15 -> 20 -> 7 , Path and are 15 + 20 + 7 = 42
Tips :
- The range of nodes in the tree is [1, 3 * 10^4]
- -1000 <= Node.val <= 1000
Their thinking
1. First, traverse the depth of the left and right subtrees , The maximum value of the current node can be divided into three cases :
- Go to the left : Current node +L( The maximum depth of the left subtree )
- Go to the right : Current node +R( The maximum depth of the right subtree )
- Don't go : If the current node is negative , Go straight back to 0
2. Then define the maximum path and ans Root node + The left subtree + Maximum depth of right subtree
3. Last , After recursion, return the maximum path and ans that will do
Code
/** * 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;
// Go down from the current node
function dfs(root) {
if(!root) return 0;
// Traversing the depth of the left subtree
let left = dfs(root.left);
// Traverse the depth of the right subtree
let right = dfs(root.right);
// The maximum value of the update path
ans = Math.max(ans, root.val + left + right);
// Return the maximum value from the current node
return Math.max(0, Math.max(left, right) + root.val);
}
};
边栏推荐
猜你喜欢
【嵌入式】Cortex M4F DSP库
[today in history] February 13: the father of transistors was born The 20th anniversary of net; Agile software development manifesto was born
C語言雙指針——經典題型
深度剖析C语言数据在内存中的存储
Mobile phones and computers on the same LAN access each other, IIS settings
Using C language to complete a simple calculator (function pointer array and callback function)
【嵌入式】使用JLINK RTT打印log
Esp8266-rtos IOT development
深度剖析C语言指针
MongoDB 的安装和基本操作
随机推荐
ant-design的走马灯(Carousel)组件在TS(typescript)环境中调用prev以及next方法
LeetCode:836. 矩形重叠
数学建模2004B题(输电问题)
[embedded] cortex m4f DSP Library
[NVIDIA development board] FAQ (updated from time to time)
View computer devices in LAN
Computer graduation design PHP Zhiduo online learning platform
TDengine 社区问题双周精选 | 第三期
Purpose of computer F1-F12
LeetCode:124. 二叉树中的最大路径和
如何进行接口测试测?有哪些注意事项?保姆级解读
Guangzhou will promote the construction of a child friendly city, and will explore the establishment of a safe area 200 meters around the school
可变长参数
Alibaba cloud server mining virus solution (practiced)
Sublime text using ctrl+b to run another program without closing other runs
The harm of game unpacking and the importance of resource encryption
What is the role of automated testing frameworks? Shanghai professional third-party software testing company Amway
LeetCode:26. 删除有序数组中的重复项
LeetCode:836. Rectangle overlap
Navicat Premium 创建MySql 创建存储过程