aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-24 18:12:23 -0700
committerJack Sangdahl <[email protected]>2024-12-24 18:12:23 -0700
commitfe6e689f0e172de9d58a2d94fa55a438813464ba (patch)
treebe3c330d49ce766dd1c967964035bc57c935a39c
parent25db68c01af00345a3525e4bcb35dca29ba5c3b3 (diff)
downloadleetcode-fe6e689f0e172de9d58a2d94fa55a438813464ba.tar.gz
leetcode-fe6e689f0e172de9d58a2d94fa55a438813464ba.zip
515. find largest value in each tree row
-rw-r--r--find_largest_val_tree.c72
-rw-r--r--find_largest_value_tree_row.c56
-rw-r--r--find_largest_value_tree_row.py (renamed from find_largest_val_tree.py)25
3 files changed, 69 insertions, 84 deletions
diff --git a/find_largest_val_tree.c b/find_largest_val_tree.c
deleted file mode 100644
index 35678f2..0000000
--- a/find_largest_val_tree.c
+++ /dev/null
@@ -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_value_tree_row.c b/find_largest_value_tree_row.c
new file mode 100644
index 0000000..d4e3399
--- /dev/null
+++ 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_val_tree.py b/find_largest_value_tree_row.py
index b47375e..ff65b3f 100644
--- a/find_largest_val_tree.py
+++ b/find_largest_value_tree_row.py
@@ -1,22 +1,19 @@
# 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)
+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]
+ """
+ :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]
@@ -25,5 +22,9 @@ class Solution(object):
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
+ 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))