leetcode:124. 二叉树中的最大路径和
2024-09-04 20:07:24
题目描述:
给定一个非空二叉树,返回其最大路径和。
本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。
示例 1:
输入: [1,2,3] 1
/ \
2 3 输出: 6 示例 2:
输入: [-10,9,20,null,null,15,7] -10
/ \
9 20
/ \
15 7 输出: 42
思路分析:
路径问题常规想到的就是用搜索解决。这道题用到了dfs,用递归完成。对于每个结点,计算其左右子树的贡献值,更新当前的最大路径为原始最大路径和左子树贡献加当前结点加右子树贡献和中较大的一个。需要注意的是计算左右子树贡献的时候,需要将取贡献值和0中的较大值,因为结点权值可能为负。同时递归函数的返回值应该为左右子树中贡献较大的加上当前结点权值。
时间复杂度为O(n),n为树中结点个数。
代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int max_sum = INT_MIN;
int get_max(TreeNode* cur)
{
if(cur == NULL)
return ;
int leftmax = max(get_max(cur->left), );
int rightmax = max(get_max(cur->right), );
max_sum = max(max_sum, leftmax+cur->val+rightmax);
return max(leftmax, rightmax) + cur->val;
}
int maxPathSum(TreeNode* root) {
if(!root)
return ;
get_max(root);
return max_sum;
}
};
最新文章
- [实践] Android5.1.1源码 - 在Framework中添加自定义系统服务
- BT客户端实现 Peer协议设计
- oracle使用sqlplus创建表空间
- asp.net gridview 鼠标悬浮提示信息
- Blackfin DSP(八):1D DMA与音频处理模板
- 情定XMLA,割舍不下的XAML
- WPF:带复选框CheckBox的树TreeView
- UITableViewCell和UITableViewHeaderFooterView的重用
- unity 引用 移动mm 支付sdk
- asp.net 弹出式日历控件 选择日期 Calendar控件
- Unity3d BTDF实时折射模拟有粗糙度的半透明物体
- CI 笔记(easyui js命令)
- 实验三:gdb跟踪调试内核从start_kernel到init进程启动
- 校门外的树 OpenJudge 1.6.06
- Django(一)入门基础——hello world
- jQuery之animate中的queue
- python----csv的使用
- 7.26-Codeforces Round #372 (Div. 2)
- Wordpress 更新时 不输入ftp相关信息的方法
- Log4j按级别输出日志到不同文件配置