diff options
-rw-r--r-- | contaminated_binary_tree.c | 80 | ||||
-rw-r--r-- | contaminated_binary_tree.py | 69 |
2 files changed, 149 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); +} diff --git a/contaminated_binary_tree.py b/contaminated_binary_tree.py new file mode 100644 index 0000000..25cc339 --- /dev/null +++ b/contaminated_binary_tree.py @@ -0,0 +1,69 @@ +# 1261. Find Elements in a Contaminated Binary Tree + +""" +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. +""" + + +# 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.right = right + + +class FindElements(object): + def __init__(self, root): + """ + :type root: Optional[TreeNode] + """ + + def recover(root, val): + return ( + root + and {val} + | recover(root.left, 2 * val + 1) + | recover(root.right, 2 * val + 2) + or set() + ) + + self.find = recover(root, 0).__contains__ + + +if __name__ == "__main__": + r1 = TreeNode(-1) + r1.left = None + r1.right = TreeNode(-1) + r2 = TreeNode(-1) + r2.left = TreeNode(-1) + r2.right = TreeNode(-1) + r2.left.left = TreeNode(-1) + r2.left.right = TreeNode(-1) + r3 = TreeNode(-1) + r3.left = None + r3.right = TreeNode(-1) + r3.right.left = TreeNode(-1) + r3.right.right = None + r3.right.left.left = TreeNode(-1) + r3.right.left.right = None + o1 = FindElements(r1) + o2 = FindElements(r2) + o3 = FindElements(r3) + print(o1.find(1)) + print(o1.find(2)) + print(o2.find(1)) + print(o2.find(3)) + print(o2.find(5)) + print(o3.find(2)) + print(o3.find(3)) + print(o3.find(4)) + print(o3.find(5)) |