diff options
author | Jack Sangdahl <[email protected]> | 2024-09-13 09:50:03 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-09-13 09:50:03 -0600 |
commit | f6175e306d3fb120d8f83804f57467fca72c9baf (patch) | |
tree | b737f66d4b0890f80cbed7943f41acdd92fb4a47 | |
parent | c7d492eb54368a4280b9e4b001cc6eb07effb51a (diff) | |
download | leetcode-f6175e306d3fb120d8f83804f57467fca72c9baf.tar.gz leetcode-f6175e306d3fb120d8f83804f57467fca72c9baf.zip |
124. binary tree maximum path sum
-rw-r--r-- | bt_max_path_sum.c | 38 | ||||
-rw-r--r-- | bt_max_path_sum.cpp | 10 | ||||
-rw-r--r-- | bt_max_path_sum.py | 43 |
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])) |