LeetCode binary-tree-maximum-path-sum

给定一个非空二叉树,返回其最大路径和。

本题中,路径被定义为一条从树中任意节点出发,达到任意节点的序列。该路径至少包含一个节点,且不一定经过根节点。 示例 1: > 输入: [1,2,3] > 1 > /
> 2 3 > 输出: 6

示例 2: > 输入: [-10,9,20,null,null,15,7] > > -10 > /
> 9 20 > /
> 15 7 > 输出: 42

解答:

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
/**
* 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) {
int ans = -0x3f3f3f3f;
dfs(root, ans);
return ans;
}
int dfs(TreeNode* cur, int &ans) {
if (cur == NULL) {
return 0;
}

int left_max = dfs(cur->left, ans);
int right_max = dfs(cur->right, ans);
//已经求了左右子树最优的路径 那dfs每个结点都跑一次,连起来看看能不能更优
ans = max(ans, left_max + right_max + cur->val);//就是连起来
//当然也可以不连。。。漏了情况
ans = max(ans, left_max + cur->val);
ans = max(ans, right_max + cur->val);
//又漏了 什么都不要
ans = max(ans, cur->val);

return max(max(left_max, right_max) + cur->val, cur->val);
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×