mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
37 lines
1.5 KiB
Markdown
37 lines
1.5 KiB
Markdown
# [124. Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/)
|
||
|
||
# 思路
|
||
|
||
给定一棵二叉树，求最大路径和，路径的起始和结尾可以是任意节点。
|
||
|
||
这题的难点就在于起始点和结尾点都可以是任意节点，如果要求起始点就是根节点那就好做很多。我们设`maxRootPathSum(root)`代表以`root`为起始结点的路径最大和，那题目要求的`maxPathSum(root)`是候选值可能是多少呢？很简单，我们可以计算`root`左右两个子结点的`maxRootPathSum`，那么`maxPathSum(root)`就可能等于`root->val + maxPathSum(root->left) + maxPathSum(root->right)`。所以我们可以用一个类似后序遍历的递归函数来实现`maxPathSum(root)`，在这个递归函数中用一个全局变量res记录遇到的最大的`maxPathSum`。
|
||
|
||
> 总结：由于二叉树本来就是通过递归定义的，所以二叉树的题很多可以用递归来做，而且多数时候就是类似遍历一遍二叉树。
|
||
|
||
相当于就是后序遍历，所以复杂度为O(n)。
|
||
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
private:
|
||
int res = INT_MIN;
|
||
int maxRootPathSum(TreeNode* root){
|
||
/*
|
||
以root为起始结点的路径最大和
|
||
*/
|
||
if(!root) return 0;
|
||
int l = max(maxRootPathSum(root -> left), 0);
|
||
int r = max(maxRootPathSum(root -> right), 0);
|
||
res = max(res, root -> val + l + r);
|
||
return root -> val + max(l, r);
|
||
}
|
||
public:
|
||
int maxPathSum(TreeNode* root) {
|
||
maxRootPathSum(root);
|
||
return res;
|
||
}
|
||
};
|
||
```
|
||
|