aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-13 09:50:03 -0600
committerJack Sangdahl <[email protected]>2024-09-13 09:50:03 -0600
commitf6175e306d3fb120d8f83804f57467fca72c9baf (patch)
treeb737f66d4b0890f80cbed7943f41acdd92fb4a47
parentc7d492eb54368a4280b9e4b001cc6eb07effb51a (diff)
downloadleetcode-f6175e306d3fb120d8f83804f57467fca72c9baf.tar.gz
leetcode-f6175e306d3fb120d8f83804f57467fca72c9baf.zip
124. binary tree maximum path sum
-rw-r--r--bt_max_path_sum.c38
-rw-r--r--bt_max_path_sum.cpp10
-rw-r--r--bt_max_path_sum.py43
3 files changed, 91 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
+}
diff --git a/bt_max_path_sum.cpp b/bt_max_path_sum.cpp
index 7be19b2..ff39808 100644
--- a/bt_max_path_sum.cpp
+++ b/bt_max_path_sum.cpp
@@ -1,5 +1,15 @@
+// 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;
diff --git a/bt_max_path_sum.py b/bt_max_path_sum.py
new file mode 100644
index 0000000..679a88b
--- /dev/null
+++ b/bt_max_path_sum.py
@@ -0,0 +1,43 @@
+# 124. Binary Tree Maximum Path Sum
+
+"""
+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
+"""
+
+
+# Definition for a binary tree node.
+class TreeNode(object):
+ def __init__(self, val=0, left=None, right=None):
+ self.val = val
+ self.left = left
+ self.right = right
+
+
+class Solution(object):
+ def dfs(self, root):
+ if not root:
+ return 0
+ left = max(0, self.dfs(root.left))
+ right = max(0, self.dfs(root.right))
+ self.ans = max(self.ans, left + right + root.val)
+ return max(left, right) + root.val
+
+ def maxPathSum(self, root):
+ """
+ :type root: TreeNode
+ :rtype: int
+ """
+ self.ans = float("-inf")
+ self.dfs(root)
+ return self.ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxPathSum(root=[1, 2, 3]))
+ print(obj.maxPathSum(root=[-10, 9, 20, None, None, 15, 7]))