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 };

Loading Disqus comments...
Table of Contents