-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathmaximum-path-sum.cpp
More file actions
47 lines (39 loc) · 972 Bytes
/
maximum-path-sum.cpp
File metadata and controls
47 lines (39 loc) · 972 Bytes
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
38
39
40
41
42
43
44
45
46
47
#include "leetcode.h"
class Solution {
int maxSum_;
public:
int maxPathSumFromRoot(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftSum = maxPathSumFromRoot(root->left);
int rightSum = maxPathSumFromRoot(root->right);
// using root
int sumFromRoot = max({
root->val,
root->val + leftSum,
root->val + rightSum});
// use or not use root
maxSum_ = max({
maxSum_,
sumFromRoot,
root->val + leftSum + rightSum});
return sumFromRoot;
}
int maxPathSum(TreeNode *root) {
if (root == NULL) {
return 0;
}
maxSum_ = root->val;
maxPathSumFromRoot(root);
return maxSum_;
}
};
int main() {
// TreeNode *root = deserialize_tree(string("-2 2 1 # # 3 # # -3 # #"));
// TreeNode *root = deserialize_tree(string("1 2 # # 3 # #"));
TreeNode *root = deserialize_tree(string("-3 # #"));
Solution sol;
cout << sol.maxPathSum(root) << endl;
return 0;
}