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,
Given the below binary tree,
1 / \ 2 3
Return
» Solve this problem6
.[Thoughts]
For each node like following, there should be four ways existing for max path:
1. Node only
2. L-sub + Node
3. R-sub + Node
4. L-sub + Node + R-sub
Keep trace the four path and pick up the max one in the end.
[Code]
1: int maxPathSum(TreeNode *root) {
2: // Start typing your C/C++ solution below
3: // DO NOT write int main() function
4: int maxAcrossRoot=INT_MIN;
5: int maxEndByRoot = GetMax(root, maxAcrossRoot);
6: return std::max(maxAcrossRoot, maxEndByRoot);
7: }
8: int GetMax(TreeNode *node, int& maxAcrossRoot)
9: {
10: if(node == NULL) return 0;
11: int left = GetMax(node->left, maxAcrossRoot);
12: int right = GetMax(node->right, maxAcrossRoot);
13: int cMax = node->val;
14: if(left>0)
15: cMax+=left;
16: if(rifht>0)
17: cMax+=right;
18: maxAcrossRoot = std::max(maxAcrossRoot, cMax);
19: return std::max(
20: node->val,
21: std::max(node->val+left, node->val+right));
22: }
No comments:
Post a Comment