aboutsummaryrefslogtreecommitdiff
path: root/bt_max_path_sum.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'bt_max_path_sum.cpp')
-rw-r--r--bt_max_path_sum.cpp21
1 files changed, 21 insertions, 0 deletions
diff --git a/bt_max_path_sum.cpp b/bt_max_path_sum.cpp
new file mode 100644
index 0000000..7be19b2
--- /dev/null
+++ b/bt_max_path_sum.cpp
@@ -0,0 +1,21 @@
+#include "leetcode.h"
+
+class Solution {
+public:
+ int sum;
+ int maxPathSum(TreeNode *root) {
+ sum = INT_MIN;
+ solve(root);
+ return sum;
+ }
+
+private:
+ int solve(TreeNode *root) {
+ if (!root)
+ return 0;
+ int left = max(0, solve(root->left));
+ int right = max(0, solve(root->right));
+ sum = max(sum, left + right + root->val);
+ return max(left, right) + root->val;
+ }
+};