diff options
Diffstat (limited to 'bt_max_path_sum.cpp')
-rw-r--r-- | bt_max_path_sum.cpp | 21 |
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; + } +}; |