diff options
author | Jack Sangdahl <[email protected]> | 2024-12-24 18:12:23 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-12-24 18:12:23 -0700 |
commit | fe6e689f0e172de9d58a2d94fa55a438813464ba (patch) | |
tree | be3c330d49ce766dd1c967964035bc57c935a39c | |
parent | 25db68c01af00345a3525e4bcb35dca29ba5c3b3 (diff) | |
download | leetcode-fe6e689f0e172de9d58a2d94fa55a438813464ba.tar.gz leetcode-fe6e689f0e172de9d58a2d94fa55a438813464ba.zip |
515. find largest value in each tree row
-rw-r--r-- | find_largest_val_tree.c | 72 | ||||
-rw-r--r-- | find_largest_value_tree_row.c | 56 | ||||
-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)) |