aboutsummaryrefslogtreecommitdiff
path: root/other/bt_max_path_sum.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'other/bt_max_path_sum.cpp')
-rw-r--r--other/bt_max_path_sum.cpp31
1 files changed, 31 insertions, 0 deletions
diff --git a/other/bt_max_path_sum.cpp b/other/bt_max_path_sum.cpp
new file mode 100644
index 0000000..ff39808
--- /dev/null
+++ b/other/bt_max_path_sum.cpp
@@ -0,0 +1,31 @@
+// 124. Binary Tree Maximum Path Sum
+#include "leetcode.h"
+
+/*
+ * a path in a binary tree is a sequence of nodes where each pair of adjacent
+ * nodes in the sequence has an edge connecting them. a node can only appear in
+ * the sequence at most once. note that the path does not need to pass through
+ * the root. the path sum of a path is the sum of the node's value in the path.
+ * given the 'root' of a binary tree, return the maximum path sum of any non
+ * empty path
+ */
+
+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;
+ }
+};