## Sunday, January 20, 2013

### [LeetCode] Binary Tree Maximum Path Sum Solution

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 `6`.
» Solve this problem

[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:    }
``````