Task
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
Example 1:
1
2
3
4
5
6
7
|
Input: [1,2,3]
1
/ \
2 3
Output: 6
|
Example 2:
1
2
3
4
5
6
7
8
9
|
Input: [-10,9,20,null,null,15,7]
-10
/ \
9 20
/ \
15 7
Output: 42
|
Solution
- 使用递归遍历树，叶子节点是终止条件，从叶子往根走。
- 遍历到一个节点root时，对于经过root这棵子树的path，分3种情况，如下图：
- path不经过root节点，而是在root的子节点中。这种情况在遍历到root之前就已被处理，不予考虑
- path经过root节点，且整个path在root这棵子树中。这种情况下需计算root左子树（或0）和右子树（或0）的sum，并加上root节点的值作为sum。更新max_sum时比较这个sum与max_sum，因为只有这个sum是由一条完整path得到的
- path经过root节点，且将延伸至root的父节点。这种情况下只需计算root的一棵子树（左子树或右子树，选大者）的sum（或0），并加上root节点的值，作为递归函数的返回值传递给父节点
- 维护一个全局的max_sum，当算出某个sum的数值比max_sum大时更新max_sum
- 花花酱的讲义如下图
- 时间复杂度：只需遍历每个节点，每个节点需要从左右子节点中得到的信息是包含该子节点且向上延伸的path的最大sum，该值可作为返回值，不需要额外计算，故时间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
// Runtime: 40 ms, faster than 78.03% of C++ online submissions for Binary Tree Maximum Path Sum.
// Memory Usage: 28.7 MB, less than 28.54% of C++ online submissions for Binary Tree Maximum Path Sum.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int maxPathSum(TreeNode* root) {
traverse(root);
return max_sum;
}
private:
int traverse(TreeNode *root){
if(!root) return 0;
//将左右子树的返回值和0比较，若小于0则不取
int l=max(0,traverse(root->left));
int r=max(0,traverse(root->right));
//上述第二种情况，是一条完整的path
//只有这种情况得到的是完整的path，故将其求和并与max_sum比较
int sum=root->val+l+r;
max_sum=max(sum,max_sum);
//上述第三种情况，是向上延伸的path的一半
//只有向父节点延伸的path才需要作为返回值提供给父节点
//此时只求path一端的和，即root的左子树或右子树或0
return root->val+max(l,r);
}
//记录全局的最大path sum
int max_sum=INT_MIN;
};
|