diff options
author | Jack Sangdahl <[email protected]> | 2024-10-26 00:09:07 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2024-10-26 00:09:07 -0600 |
commit | a43f21d0aff66470e17b47febcd01e67bbdce5f6 (patch) | |
tree | 56f0a0d0f02e8aa79e6a1426f8ba128552404a09 | |
parent | 54e0305c7a0927ea74163843e547dcb93d84344c (diff) | |
download | leetcode-a43f21d0aff66470e17b47febcd01e67bbdce5f6.tar.gz leetcode-a43f21d0aff66470e17b47febcd01e67bbdce5f6.zip |
2458. height of binarytree after subtree removal queries
-rw-r--r-- | height_binary_tree_removal.c | 99 | ||||
-rw-r--r-- | height_binary_tree_removal.py | 66 |
2 files changed, 165 insertions, 0 deletions
diff --git a/height_binary_tree_removal.c b/height_binary_tree_removal.c new file mode 100644 index 0000000..a54599d --- /dev/null +++ b/height_binary_tree_removal.c @@ -0,0 +1,99 @@ +// 2458. Height of Binary Tree After Subtree Removal Queries +#include "leetcode.h" + +/* + * you are given the 'root' of a binary tree with 'n' nodes. each node is + * assigned a unique value from 1 to 'n'. you are also given an array 'queries' + * of size 'm'. you have to perform 'm' independent queries on the tree where in + * the i'th query, you remove the subtree rooted at the node with the value + * 'queries[i]' from thre tree. it is guaranteed that 'queries[i]' will not be + * equal to the value of the root. return an array 'answer' of size 'm' where + * 'answer[i]' is the height of the tree after performining the i'th query + */ + +#define MAX_NODES 100001 + +struct node_info { + int height; + int level; +}; + +struct level_info { + int max_height1; + int max_height2; +}; + +struct node_info *node_map[MAX_NODES]; +struct level_info *level_map[MAX_NODES]; + +int dfs(struct TreeNode *root, int level) { + if (!root) + return 0; + int left = dfs(root->left, level + 1); + int right = dfs(root->right, level + 1); + int height = left > right ? left : right; + if (!level_map[level]) { + level_map[level] = (struct level_info *)malloc(sizeof(struct level_info)); + level_map[level]->max_height1 = -1; + level_map[level]->max_height2 = -1; + } + if (height >= level_map[level]->max_height1) { + level_map[level]->max_height2 = level_map[level]->max_height1; + level_map[level]->max_height1 = height; + } else if (height > level_map[level]->max_height2) + level_map[level]->max_height2 = height; + node_map[root->val] = (struct node_info *)malloc(sizeof(struct node_info)); + node_map[root->val]->height = height; + node_map[root->val]->level = level; + return height + 1; +} + +int *treeQueries(struct TreeNode *root, int *queries, int queriesSize, + int *returnSize) { + *returnSize = queriesSize; + int max_depth = dfs(root, 0) - 1; + int *ans = (int *)malloc(queriesSize * sizeof(int)); + for (int i = 0; i < queriesSize; i++) { + int curr = queries[i]; + struct node_info *n = node_map[curr]; + int height = n->height; + int level = n->level; + struct level_info *l = level_map[level]; + if (l->max_height1 == height) + ans[i] = l->max_height2 != -1 + ? max_depth - abs(l->max_height1 - l->max_height2) + : max_depth - 1; + else + ans[i] = max_depth; + } + for (int i = 0; i < MAX_NODES; i++) { + if (node_map[i]) { + free(node_map[i]); + node_map[i] = NULL; + } + if (level_map[i]) { + free(level_map[i]); + level_map[i] = NULL; + } + } + return ans; +} + +int main() { + struct TreeNode *root = treenode_create(5); + root->left = treenode_create(8); + root->right = treenode_create(9); + root->left->left = treenode_create(2); + root->left->right = treenode_create(1); + root->right->left = treenode_create(3); + root->right->right = treenode_create(7); + root->left->left->left = treenode_create(4); + root->left->left->right = treenode_create(6); + int queries[] = {3, 2, 4, 8}, returnSize; + int *tq = treeQueries(root, queries, ARRAY_SIZE(queries), &returnSize); + for (int i = 0; i < returnSize; i++) + printf("%d ", tq[i]); // expect: 3 2 3 2 + printf("\n"); + free(tq); + treenode_free(root); +} diff --git a/height_binary_tree_removal.py b/height_binary_tree_removal.py new file mode 100644 index 0000000..4ad028f --- /dev/null +++ b/height_binary_tree_removal.py @@ -0,0 +1,66 @@ +# 2458. Height of Binary Tree After Subtree Removal Queries +from collections import defaultdict + +""" +you are given the 'root' of a binary tree with 'n' nodes. each node is +assigned a unique value from 1 to 'n'. you are also given an array 'queries' +of size 'm'. you have to perform 'm' independent queries on the tree where in +the i'th query, you remove the subtree rooted at the node with the value +'queries[i]' from thre tree. it is guaranteed that 'queries[i]' will not be +equal to the value of the root. return an array 'answer' of size 'm' where +'answer[i]' is the height of the tree after performining the i'th query +""" + + +# 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.rGight = right + + +class Solution(object): + def treeQueries(self, root, queries): + """ + :type root: Optional[TreeNode] + :type queries: List[int] + :rtype: List[int] + """ + depth, height = defaultdict(int), defaultdict(int) + + def dfs(node, level): + if not node: + return -1 + depth[node.val] = level + curr = max(dfs(node.left, level + 1), dfs(node.right, level + 1)) + 1 + height[node.val] = curr + return curr + + dfs(root, 0) + cousins = defaultdict(list) + for val, level in depth.items(): + cousins[level].append((-height[val], val)) + cousins[level].sort() + if len(cousins[level]) > 2: + cousins[depth].pop() + ans = [] + for i in queries: + curr = depth[i] + if len(cousins[curr]) == 1: + ans.append(depth - 1) + elif cousins[curr][0][1] == i: + ans.append(-cousins[curr][1][0] + curr) + else: + ans.append(-cousins[curr][0][0] + curr) + return ans + + +if __name__ == "__main__": + obj = Solution() + print( + obj.treeQueries( + root=[1, 3, 4, 2, None, 6, 5, None, None, None, None, None, 7], queries=[4] + ) + ) + print(obj.treeQueries(root=[5, 8, 9, 2, 1, 3, 7, 4, 6], queries=[3, 2, 4, 8])) |