8000 added 126. Binary Tree Maximum Path Sum · LeetCode-Interview/LeetCode@41eacd7 · GitHub
[go: up one dir, main page]
Skip to content

Commit 41eacd7

Browse files
pezypezy
committed
added 126. Binary Tree Maximum Path Sum
1 parent 6827426 commit 41eacd7

File tree

3 files changed

+98
-0
lines changed

3 files changed

+98
-0
lines changed

‎126. Binary Tree Maximum Path Sum/README.md

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
这道题难点是个障眼法。
2+
3+
例子给出的二叉树一点代表性也没，我来给一个，说明题意：
4+
5+
1
6+
/ \
7+
2 3
8+
/ \ \
9+
4 5 6
10+
11+
我们列举一下，这里面有多少种可能的路径(限完整的路径)：
12+
13+
2 1 1
14+
/ \ / \ / \
15+
4 5 2 3 2 3
16+
(11) \ \ / \
17+
5 6 4 6
18+
(17) (16)
19+
20+
显然，咱们应该返回中间那个 sum, 是 17.这结果是咱们肉眼看出来的，需进一步分析其规律性。
21+
22+
首先，右边两个来自同一棵“大树”，为何选择了 17 呢，显然是取最大值。
23+
24+
其次，左边那棵树，实际是根节点的左子树。同理我们还可以列出其右子树：
25+
26+
3
27+
\
28+
6
29+
(9)
30+
31+
那么左子树和右子树若没有这个例子里面这样简单，也有分支呢？那么还是求其最大值即可。咦，这是否有种递归性？
32+
33+
这个例子还有一个盲点，即所有节点值皆为正数，会不会有负数？如果有负数，可能咱们不需要“完整的路径”。
34+
35+
更全局的看，如果某个子树的 max sum 是个负数，还不如没有。“没有”如何表达？是了，`sum == 0.`
36+
37+
好了，分析到这里，可以开始尝试写递归函数了：
38+
39+
```cpp
40+
int maxPathSum(TreeNode *root, int &maxSum) {
41+
if (!root) return 0;
42+
int leftMax = std::max(0, maxPathSum(root->left, maxSum));
43+
int rightMax = std::max(0, maxPathSum(root->right, maxSum));
44+
maxSum = std::max(sum, root->val + leftMax + rightMax);
45+
return root->val + std::max(leftMax, rightMax);
46+
}
47+
```
48+
49+
好像很简单的样子。主函数中，将 `maxSum` 初始化为最小值：`INT_MIN` 即可。
50+
51+
提交试试，AC.

‎126. Binary Tree Maximum Path Sum/main.cpp

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
#include "solution.h"
2+
#include <iostream>
3+
4+
int main()
5+
{
6+
Solution s;
7+
TreeNode root(1);
8+
TreeNode node1(2);
9+
TreeNode node2(3);
10+
TreeNode node3(4);
11+
TreeNode node4(5);
12+
TreeNode node5(6);
13+
14+
root.left = &node1;
15+
root.right = &node2;
16+
node1.left = &node3;
17+
node1.right = &node4;
18+
node2.right = &node5;
19+
20+
std::cout << s.maxPathSum(&root) << std::endl;
21+
}

‎126. Binary Tree Maximum Path Sum/solution.h

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
#include <cstddef>
2+
#include <algorithm>
3+
4+
struct TreeNode {
5+
int val;
6+
TreeNode *left;
7+
TreeNode *right;
8+
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9+
};
10+
11+
class Solution {
12+
int maxPathSum(TreeNode *root, int &maxSum) {
13+
if (!root) return 0;
14+
int leftMax = std::max(0, maxPathSum(root->left, maxSum));
15+
int rightMax = std::max(0, maxPathSum(root->right, maxSum));
16+
maxSum = std::max(maxSum, leftMax+rightMax+root->val);
17+
return root->val + std::max(leftMax, rightMax);
18+
}
19+
20+
public:
21+
int maxPathSum(TreeNode *root) {
22+
int maxSum = INT_MIN;
23+
maxPathSum(root, maxSum);
24+
return maxSum;
25+
}
26+
};

0 commit comments

Comments
 (0)
0