aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-10-21 19:28:33 -0600
committerJack Sangdahl <[email protected]>2024-10-21 19:28:33 -0600
commit79945065d30539dc039f0e77cf8c9fc0058ec2c7 (patch)
tree4ba9046bc28dc24fc1a82aa2262a724a52be1e9a
parent3f53cedfddf11641d652d347b25df64807a4468a (diff)
downloadleetcode-79945065d30539dc039f0e77cf8c9fc0058ec2c7.tar.gz
leetcode-79945065d30539dc039f0e77cf8c9fc0058ec2c7.zip
2583. kth largest sum in a binary tree
-rw-r--r--kth_largest_sum_binary_tree.c85
-rw-r--r--kth_largest_sum_binary_tree.py45
2 files changed, 130 insertions, 0 deletions
diff --git a/kth_largest_sum_binary_tree.c b/kth_largest_sum_binary_tree.c
new file mode 100644
index 0000000..f959783
--- /dev/null
+++ b/kth_largest_sum_binary_tree.c
@@ -0,0 +1,85 @@
+// 2583. Kth Largest Sum in a Binary Tree
+#include "leetcode.h"
+
+/*
+ * you are given the 'root' of a binary tree and a positive integer 'k'. the
+ * level sum in the tree is the sum of the values of the nodes that are on the
+ * same level. return the k'th largest level sum in the tree (not necessarily
+ * distinct). if there are fewer than 'k' levels in the tree, return -1. note
+ * that two nodes are on the same level if they have the same distance from the
+ * root.
+ */
+
+int depth(struct TreeNode *root) {
+ if (!root)
+ return 0;
+ int l = depth(root->left) + 1;
+ int r = depth(root->right) + 1;
+ return l > r ? l : r;
+}
+
+void level_sum(struct TreeNode *root, int level, long long *data) {
+ if (!root)
+ return;
+ data[level] += root->val;
+ level_sum(root->left, level + 1, data);
+ level_sum(root->right, level + 1, data);
+}
+
+void swap(long long *a, long long *b) {
+ long long tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+int partition(long long *data, int l, int h) {
+ int i = l, j = l;
+ long long pivot = data[h - 1];
+ for (j - l; j < h - 1; j++)
+ if (data[j] < pivot)
+ swap(&data[i++], &data[j]);
+ swap(&data[i], &data[h - 1]);
+ return i;
+}
+
+void quick_select(long long *data, int l, int h, int k) {
+ if (l + 1 < h) {
+ int p = partition(data, l, h);
+ if (p == k)
+ return;
+ else if (p < k)
+ quick_select(data, p + 1, h, k);
+ else
+ quick_select(data, l, p, k);
+ }
+}
+
+long long kthLargestLevelSum(struct TreeNode *root, int k) {
+ int n = depth(root);
+ if (k > n)
+ return -1;
+ long long val, *data = (long long *)calloc(n, sizeof(long long));
+ level_sum(root, 0, data);
+ quick_select(data, 0, n, n - k);
+ return data[n - k];
+}
+
+int main() {
+ struct TreeNode *r1 = treenode_create(5);
+ r1->left = treenode_create(8);
+ r1->right = treenode_create(9);
+ r1->left->left = treenode_create(2);
+ r1->left->right = treenode_create(1);
+ r1->right->left = treenode_create(3);
+ r1->right->right = treenode_create(7);
+ r1->left->left->left = treenode_create(4);
+ r1->left->left->right = treenode_create(6);
+ struct TreeNode *r2 = treenode_create(1);
+ r2->left = treenode_create(2);
+ r2->right = NULL;
+ r2->left->left = treenode_create(3);
+ printf("%lld\n", kthLargestLevelSum(r1, 2)); // expect: 13
+ printf("%lld\n", kthLargestLevelSum(r2, 1)); // expect: 3
+ treenode_free(r1);
+ treenode_free(r2);
+}
diff --git a/kth_largest_sum_binary_tree.py b/kth_largest_sum_binary_tree.py
new file mode 100644
index 0000000..8f853ba
--- /dev/null
+++ b/kth_largest_sum_binary_tree.py
@@ -0,0 +1,45 @@
+# 2583. Kth Largest Sum in a Binary Tree
+
+"""
+you are given the 'root' of a binary tree and a positive integer 'k'. the
+level sum in the tree is the sum of the values of the nodes that are on the
+same level. return the k'th largest level sum in the tree (not necessarily
+distinct). if there are fewer than 'k' levels in the tree, return -1. note
+that two nodes are on the same level if they have the same distance from the
+root.
+"""
+
+
+# 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 kthLargestLevelSum(self, root, k):
+ """
+ :type root: Optional[TreeNode]
+ :type k: int
+ :rtype: int
+ """
+ vals = []
+ stack = [(root, 0)]
+ while stack:
+ node, i = stack.pop()
+ if i == len(vals):
+ vals.append(0)
+ vals[i] += node.val
+ if node.left:
+ stack.append((node.left, i + 1))
+ if node.right:
+ stack.append((node.right, i + 1))
+ return sorted(vals, reverse=True)[k - 1] if len(vals) >= k else -1
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.kthLargestLevelSum(root=[5, 8, 9, 2, 1, 3, 7, 4, 6], k=2))
+ print(obj.kthLargestLevelSum(root=[1, 2, None, 3]))