forked from timoncui/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBinary_Tree_Maximum_Path_Sum.cpp
More file actions
61 lines (49 loc) · 1.43 KB
/
Binary_Tree_Maximum_Path_Sum.cpp
File metadata and controls
61 lines (49 loc) · 1.43 KB
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/*
Author: Timon Cui, [email protected]
Title: Binary Tree Maximum Path Sum
Description:
Given a binary tree, find the maximum path sum.
The path may start and end at any node in the tree.
For example:
Given the below binary tree,
1
/ \
2 3
Return 1 + 2 + 3 = 6
Difficulty rating: Medium
Source:
http://www.leetcode.com/onlinejudge
Notes:
Post order traverse, keep track of max sum on left and right.
Similar to max subarray problem.
https://github.com/timoncui/LeetCode/blob/master/Maximum_Subarray.cpp
*/
/**
* Definition for binary tree
* 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 dummy;
return maxPathSum(root, &dummy);
}
private:
int pos(int v) { return v > 0 ? v : 0; }
int maxPathSum(TreeNode *root, int *max_ending_here) {
if (root == NULL) {
*max_ending_here = INT_MIN;
return INT_MIN;
}
int max_ending_left, max_ending_right;
int max_left = maxPathSum(root->left, &max_ending_left);
int max_right = maxPathSum(root->right, &max_ending_right);
*max_ending_here = root->val + pos(max(max_ending_left, max_ending_right));
return max(max(max_left, max_right), root->val + pos(max_ending_left) + pos(max_ending_right));
}
};