commit fe6e689f0e172de9d58a2d94fa55a438813464ba
parent 25db68c01af00345a3525e4bcb35dca29ba5c3b3
Author: Jack Sangdahl <jack@pngu.org>
Date: Tue, 24 Dec 2024 18:12:23 -0700
515. find largest value in each tree row
Diffstat:
4 files changed, 86 insertions(+), 101 deletions(-)
diff --git a/find_largest_val_tree.c b/find_largest_val_tree.c
@@ -1,72 +0,0 @@
-// 515. Find Largest Value in Each Tree Row
-#include "leetcode.h"
-
-/*
- * given the 'root' of a binary tree, return an array of the largest value in
- * each row of the tree (0-indexed)
- */
-
-struct TreeNode {
- int val;
- struct TreeNode *left;
- struct TreeNode *right;
-};
-
-int depth(struct TreeNode *root) {
- if (!root)
- return 0;
- else
- return 1 + fmax(depth(root->left), depth(root->right));
-}
-
-int *largestValues(struct TreeNode *root, int *return_size) {
- int dep = depth(root);
- if (!dep) {
- *return_size = 0;
- return 0;
- }
- int *ans = malloc(dep * sizeof(int));
- int ans_idx = 0, idx0 = 0, idx1 = 0;
- struct TreeNode **q0 = malloc(5000 * sizeof(struct TreeNode *));
- struct TreeNode **q1 = malloc(5000 * sizeof(struct TreeNode *));
- q0[idx0] = root;
- idx0 = 1;
- while (idx0 || idx1) {
- int max = INT_MIN;
- if (idx0) {
- for (int i = 0; i < idx0; i++) {
- if (q0[i]->val > max)
- max = q0[i]->val;
- if (q0[i]->left) {
- q1[idx1] = q0[i]->left;
- idx1++;
- }
- if (q0[i]->right) {
- q1[idx1] = q0[i]->right;
- idx1++;
- }
- }
- ans[ans_idx] = max;
- ans_idx++;
- idx0 = 0;
- } else {
- for (int i = 0; i < idx1; i++) {
- if (q1[i]->val > max)
- max = q1[i]->val;
- if (q1[i]->left) {
- q0[idx0] = q1[i]->left;
- idx0++;
- }
- if (q1[i]->right) {
- q0[idx0] = q1[i]->right;
- idx0++;
- }
- }
- ans[ans_idx] = max;
- ans_idx++;
- idx1 = 0;
- }
- }
- *return_size = ans_idx;
- return ans;
-}
diff --git a/find_largest_val_tree.py b/find_largest_val_tree.py
@@ -1,29 +0,0 @@
-# 515. Find Largest Value in Each Tree Row
-
-"""
-given the 'root' of a binary tree, return an array of the largest value in
-each row of the tree (0-indexed)
-"""
-
-
-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 largestValues(self, root):
- ans = []
- row = [root]
- while any(row):
- ans.append(max(node.val for node in row))
- row = [child for node in row for child in (node.left, node.right) if child]
- return ans
-
-
-if __name__ == "__main__":
- obj = Solution()
- print(obj.largestValues(root=[1, 3, 2, 5, 3, null, 9])) # expect: 1, 3, 9
- print(obj.largestValues(root=[1, 2, 3])) # expect: 1, 3
diff --git a/find_largest_value_tree_row.c b/find_largest_value_tree_row.c
@@ -0,0 +1,56 @@
+// 515. Find Largest Value in Each Tree Row
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree, return an array of the largest value in
+ * each row of the tree (0-indexed).
+ */
+
+void pre_order(struct TreeNode *node, int level, int *arr, int *size) {
+ if (!node)
+ return;
+ if (*size <= level) {
+ (*size)++;
+ arr[level] = INT_MIN;
+ }
+ arr[level] = arr[level] > node->val ? arr[level] : node->val;
+ pre_order(node->left, level + 1, arr, size);
+ pre_order(node->right, level + 1, arr, size);
+}
+
+int *largestValues(struct TreeNode *root, int *returnSize) {
+ if (!root) {
+ *returnSize = 0;
+ return NULL;
+ }
+ int n = 0, arr[10001];
+ pre_order(root, 0, arr, &n);
+ *returnSize = n;
+ int *ans = (int *)malloc(n * sizeof(int));
+ for (int i = 0; i < n; i++)
+ ans[i] = arr[i];
+ return ans;
+}
+
+int main() {
+ struct TreeNode *r1 = treenode_create(1);
+ r1->left = treenode_create(3);
+ r1->right = treenode_create(2);
+ r1->left->left = treenode_create(5);
+ r1->left->right = treenode_create(3);
+ r1->right->right = treenode_create(9);
+ struct TreeNode *r2 = treenode_create(1);
+ r2->left = treenode_create(2);
+ r2->right = treenode_create(3);
+ int rs1, rs2;
+ int *lv1 = largestValues(r1, &rs1);
+ int *lv2 = largestValues(r2, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", lv1[i]); // expect: 1 3 9
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", lv2[i]); // expect: 1 3
+ printf("\n");
+ free(lv1), free(lv2);
+ treenode_free(r1), treenode_free(r2);
+}
diff --git a/find_largest_value_tree_row.py b/find_largest_value_tree_row.py
@@ -0,0 +1,30 @@
+# 515. Find Largest Value in Each Tree Row
+import leetcode
+
+"""
+given the 'root' of a binary tree, return an array of the largest value in
+each row of the tree (0-indexed).
+"""
+
+
+class Solution(object):
+ def largestValues(self, root):
+ """
+ :type root: Optional[TreeNode]
+ :rtype: List[int]
+ """
+ ans, row = [], [root]
+ while any(row):
+ ans.append(max(node.val for node in row))
+ row = [child for node in row for child in (node.left, node.right) if child]
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ r1i = [1, 3, 2, 5, 3, None, 9]
+ r2i = [1, 2, 3]
+ r1 = leetcode.list_to_tree(r1i)
+ r2 = leetcode.list_to_tree(r2i)
+ print(obj.largestValues(r1))
+ print(obj.largestValues(r2))
