【LeetCode】124. Binary Tree Maximum Path Sum 解题报告 (C++)
2024-09-06 18:47:12
- 作者: 负雪明烛
- id: fuxuemingzhu
- 个人博客:http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/binary-tree-maximum-path-sum/
题目描述
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 3
Output: 6
Example 2:
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
题目大意
找出二叉树中的最大路径和。
解题方法
递归
路径是我们可以从二叉树中任意选择1个或者多个相邻的节点而构成的。那么对于每个节点,我们是不是可以考虑他的左孩子是否考虑到路径内,右孩子是否考虑到路径内,从而产生公式:
经过一个节点的最大路径 = max(其左孩子为顶点的最大路径, 0) + max(右孩子为顶点的最大路径, 0) + 该节点的值。
公式里对左右孩子为顶点的最大路径和0取max,是因为路径可能是负值,加入左右孩子的最大路径为负数,那么就不应该使用了。
为什么左右孩子要为顶点的时候才行呢?一条路径不应该有分叉的,所以如果想求经过一个节点的路径的话,那么左右孩子那里不能分叉,必须是以左右孩子为出发点的一条路径:
2
/ \
9 20
/ \
15 7
最大路径是9 + 2 + 20 + 15
C++代码如下:
/**
* 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 maxPathSum(TreeNode* root) {
if (!root) return 0;
maxPathToLeaf(root);
return res;
}
int maxPathToLeaf(TreeNode* root) {
if (!root) return 0;
int left = maxPathToLeaf(root->left);
int right = maxPathToLeaf(root->right);
if (left < 0)
left = 0;
if (right < 0)
right = 0;
res = max(res, left + right + root->val);
return root->val + max(left, right);
}
private:
int res = INT_MIN;
};
相似题目
日期
2019 年 9 月 27 日 —— 昨天面快手,竟然是纯刷题
最新文章
- 五一干货来袭!开源Moon.Orm标准版发布!
- tableLayoutPanel的使用
- 【Oracle XE系列之一】Windows10_X64环境 安装Oracle XE11gR2 X64数据库
- SQL SERVER 2008 登陆失败(SQL和windows都没有对应的权限)
- [Shell] 读取脚本路径
- css中的定位和框模型问题
- 高性能的分布式内存对象缓存系统Memcached
- ASPxTreeList控件去根节点的新增修改操作(写在onCommandColumnButtonInitialize()事件中)
- numa对MySQL多实例性能影响
- Spark SQL概念学习系列之SQL on Spark的简介(三)
- Weblogic 10.3.6 在RHEL5.4 下安装
- Android_layout_note
- layerX &;&; layerY
- 跟我一起学写jQuery插件开发方法(转载)
- 从ICassFactory为CLSID为{17BCA6E8-A950-497E-B2F9-AF6AA475916F}的COM组件创建实例失败,原因是出现以下错误:c001f011.(Microsoft.Server.manageDTS
- [刷题]算法竞赛入门经典(第2版) 5-7/UVa12100 - Printer Queue
- ML笔记:Where does the error come from?
- 从码云上下载react项目并配置成可运行状态
- java-自动登录 与 记住用户名
- 以太坊go-ethereum客户端(三)两种全节点启动模式