[LeetCode] Binary Tree Maximum Path Sum

 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 public:
12     bool is_valid_ = false;
13     int max_sum = INT_MIN;
14     int maxPathSum(TreeNode *root) {
15         if (root == NULL) return max_sum;
16         Dfs(root);
17         is_valid_ = true;
18         return max_sum;
19     }
20     
21     //后序递归
22     int Dfs(TreeNode *root) {
23         if (root == NULL) return 0;
24         int left_sum = Dfs(root->left);
25         int right_sum = Dfs(root->right);
26         int current_sum = root->val;
27         if (left_sum > 0) current_sum += left_sum;
28         if (right_sum > 0) current_sum += right_sum;
29         max_sum = max(max_sum, current_sum);
30         
31         return max(left_sum, right_sum) > 0 ? max(left_sum, right_sum) + root->val : root->val;
32     }
33 };