# binary tree maxnum path sum

## binary tree maxnum path sum

### Search

Using result to keep the max value of the path. When search to a node, result = maxnum of these:

• result
• `node->val`
• `node->val`+ the path sum of node's left child.
• `node->val`+ the path sum of node's right child.
• `node->val`+ the path sum of both node's left and right child.
Using a function to caculate the max path with the node argument, at the same time uptate the result.
`````` 1 /**
2  * Definition for binary tree
3  * struct TreeNode {
4  *     int val;
5  *     TreeNode *left;
6  *     TreeNode *right;
7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
8  * };
9  */
10 class Solution {
11 private:
12     int result;
13 public:
14     int maxPathSum(TreeNode *root) {
15         result = root->val;
16         connectPath(root);
17         return result;
18     }
19     int connectPath( TreeNode* root ) {
20         if ( !root ) {
21             return 0;
22         }
23         int val = root->val;
24         result = max(result,val);
25         int left = connectPath(root->left);
26         int right = connectPath(root->right);
27         if ( left > 0 ) {
28             val += left;
29         }
30         if ( right > 0 ) {
31             val += right;
32         }
33         result = max(result,val);
34         return max(left,right) > 0 ? max(left,right)+root->val : root->val;
35     }
36 };``````