aboutsummaryrefslogtreecommitdiff
path: root/bt_max_path_sum.c
diff options
context:
space:
mode:
Diffstat (limited to 'bt_max_path_sum.c')
-rw-r--r--bt_max_path_sum.c38
1 files changed, 38 insertions, 0 deletions
diff --git a/bt_max_path_sum.c b/bt_max_path_sum.c
new file mode 100644
index 0000000..3812897
--- /dev/null
+++ b/bt_max_path_sum.c
@@ -0,0 +1,38 @@
+// 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
+ */
+
+int dfs(struct TreeNode *root, int *max) {
+ if (!root)
+ return 0;
+ int left = dfs(root->left, max);
+ int right = dfs(root->right, max);
+ left = fmax(left, 0);
+ right = fmax(right, 0);
+ int curr = left + root->val + right;
+ *max = fmax(*max, curr);
+ return root->val + fmax(left, right);
+}
+
+int maxPathSum(struct TreeNode *root) {
+ int ans = INT_MIN;
+ dfs(root, &ans);
+ return ans;
+}
+
+int main() {
+ struct TreeNode *root = treenode_create(-10);
+ root->left = treenode_create(9);
+ root->right = treenode_create(20);
+ root->right->left = treenode_create(15);
+ root->right->right = treenode_create(7);
+ printf("%d\n", maxPathSum(root)); // expect: 42
+}