diff options
Diffstat (limited to 'contaminated_binary_tree.c')
-rw-r--r-- | contaminated_binary_tree.c | 80 |
1 files changed, 80 insertions, 0 deletions
diff --git a/contaminated_binary_tree.c b/contaminated_binary_tree.c new file mode 100644 index 0000000..488654f --- /dev/null +++ b/contaminated_binary_tree.c @@ -0,0 +1,80 @@ +// 1261. Find Elements in a Contaminated Binary Tree +#include "leetcode.h" + +/* + * given a binary tree with the following rules: 'root.val == 0', for any + * 'TreeNode': if 'TreeNode.val' has a value 'x' and 'TreeNode.left != null' + * then 'TreeNode.left.val == 2 * x + 1', and if 'TreeNode.val' has a value 'x' + * and 'TreeNode.right != null', then 'TreeNode.right.val = 2 * x + 2'. now the + * binary tree is contaminated which means all 'TreeNode.val' have been changed + * to -1. implemented the 'FindElements' class: 'findElementsCreate': + * initialises the object with a contaminated tree and recovers it. 'bool + * find(int target)' returns 'true' if the 'target' value exists in the + * recovered binary tree. + */ + +typedef struct { + int map[10000]; + int map_size; +} FindElements; + +void recover(FindElements *obj, struct TreeNode *node, int val) { + obj->map[obj->map_size] = val; + obj->map_size++; + if (node->left) + recover(obj, node->left, val * 2 + 1); + if (node->right) + recover(obj, node->right, val * 2 + 2); + return; +} + +FindElements *findElementsCreate(struct TreeNode *root) { + FindElements *tree = (FindElements *)calloc(1, sizeof(FindElements)); + recover(tree, root, 0); + return tree; +} + +bool findElementsFind(FindElements *obj, int target) { + for (int i = 0; i < obj->map_size; i++) + if (obj->map[i] == target) + return true; + return false; +} + +void findElementsFree(FindElements *obj) { free(obj); } + +int main() { + struct TreeNode *r1 = treenode_create(-1); + r1->left = NULL; + r1->right = treenode_create(-1); + struct TreeNode *r2 = treenode_create(-1); + r2->left = treenode_create(-1); + r2->right = treenode_create(-1); + r2->left->left = treenode_create(-1); + r2->left->right = treenode_create(-1); + struct TreeNode *r3 = treenode_create(-1); + r3->left = NULL; + r3->right = treenode_create(-1); + r3->right->left = treenode_create(-1); + r3->right->right = NULL; + r3->right->left->left = treenode_create(-1); + r3->right->left->right = NULL; + FindElements *o1 = findElementsCreate(r1); + FindElements *o2 = findElementsCreate(r2); + FindElements *o3 = findElementsCreate(r3); + printf("%d\n", findElementsFind(o1, 1)); // expect: 0 + printf("%d\n", findElementsFind(o1, 2)); // expect: 1 + printf("%d\n", findElementsFind(o2, 1)); // expect: 1 + printf("%d\n", findElementsFind(o2, 3)); // expect: 1 + printf("%d\n", findElementsFind(o2, 5)); // expect: 0 + printf("%d\n", findElementsFind(o3, 2)); // expect: 1 + printf("%d\n", findElementsFind(o3, 3)); // expect: 0 + printf("%d\n", findElementsFind(o3, 4)); // expect: 0 + printf("%d\n", findElementsFind(o3, 5)); // expect: 1 + findElementsFree(o1); + findElementsFree(o2); + findElementsFree(o3); + treenode_free(r1); + treenode_free(r2); + treenode_free(r3); +} |