aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--contaminated_binary_tree.c80
-rw-r--r--contaminated_binary_tree.py69
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))