{"id":5872,"date":"2019-11-26T17:10:41","date_gmt":"2019-11-27T01:10:41","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5872"},"modified":"2019-11-26T17:30:08","modified_gmt":"2019-11-27T01:30:08","slug":"leetcode-1261-find-elements-in-a-contaminated-binary-tree","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/tree\/leetcode-1261-find-elements-in-a-contaminated-binary-tree\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1261. Find Elements in a Contaminated Binary Tree"},"content":{"rendered":"\n<p>Given a&nbsp;binary tree with the following rules:<\/p>\n\n\n\n<ol class=\"wp-block-list\"><li><code>root.val == 0<\/code><\/li><li>If&nbsp;<code>treeNode.val == x<\/code>&nbsp;and&nbsp;<code>treeNode.left != null<\/code>, then&nbsp;<code>treeNode.left.val == 2 * x + 1<\/code><\/li><li>If&nbsp;<code>treeNode.val == x<\/code>&nbsp;and&nbsp;<code>treeNode.right != null<\/code>, then&nbsp;<code>treeNode.right.val == 2 * x + 2<\/code><\/li><\/ol>\n\n\n\n<p>Now the binary tree is contaminated, which means all&nbsp;<code>treeNode.val<\/code>&nbsp;have&nbsp;been changed to&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>You need to first recover the binary tree and then implement the&nbsp;<code>FindElements<\/code>&nbsp;class:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>FindElements(TreeNode* root)<\/code>&nbsp;Initializes the object with a&nbsp;contamined binary tree, you need to recover it first.<\/li><li><code>bool find(int target)<\/code>&nbsp;Return if the&nbsp;<code>target<\/code>&nbsp;value exists in the recovered binary tree.<\/li><\/ul>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/06\/untitled-diagram-4-1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"FindElements\",\"find\",\"find\"]\n[[[-1,null,-1]],[1],[2]]\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,false,true]<\/p>\n\n\n\n<p><strong>Explanation<\/strong>\nFindElements findElements = new FindElements([-1,null,-1]); \nfindElements.find(1); \/\/ return False \nfindElements.find(2); \/\/ return True <\/p>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/06\/untitled-diagram-4.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"FindElements\",\"find\",\"find\",\"find\"]\n[[[-1,-1,-1,-1,-1]],[1],[3],[5]]\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,true,true,false]<\/p>\n\n\n\n<p><strong>Explanation<\/strong>\nFindElements findElements = new FindElements([-1,-1,-1,-1,-1]);\nfindElements.find(1); \/\/ return True\nfindElements.find(3); \/\/ return True\nfindElements.find(5); \/\/ return False<\/p>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2019\/11\/07\/untitled-diagram-4-1-1.jpg\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input<\/strong>\n[\"FindElements\",\"find\",\"find\",\"find\",\"find\"]\n[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]\n<strong>Output<\/strong>\n<\/pre>\n\n\n<p>[null,true,false,false,true]<\/p>\n\n\n\n<p><strong>Explanation<\/strong>\nFindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);\nfindElements.find(2); \/\/ return True\nfindElements.find(3); \/\/ return False\nfindElements.find(4); \/\/ return False\nfindElements.find(5); \/\/ return True\n<\/p>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>TreeNode.val == -1<\/code><\/li><li>The height of the binary tree is less than or equal to&nbsp;<code>20<\/code><\/li><li>The total number of nodes is between&nbsp;<code>[1,&nbsp;10^4]<\/code><\/li><li>Total calls of&nbsp;<code>find()<\/code>&nbsp;is between&nbsp;<code>[1,&nbsp;10^4]<\/code><\/li><li><code>0 &lt;= target &lt;= 10^6<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solutoin 1: Recursion and HashSet<\/strong><\/h2>\n\n\n\n<p>Time complexity: Recover O(n), find O(1)<br>Space complexity: O(n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\/\/ Author: Huahua\nclass FindElements {\npublic:\n  FindElements(TreeNode* root) {\n    recover(root, 0);\n  }\n\n  bool find(int target) {\n    return s_.count(target);\n  }\nprivate:\n  unordered_set<int> s_;\n  void recover(TreeNode* root, int val) {\n    if (!root) return;\n    root->val = val;\n    s_.insert(val);\n    recover(root->left, val * 2 + 1);\n    recover(root->right, val * 2 + 2);\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 2: Recursion and Binary format<\/strong><\/h2>\n\n\n\n<p>The binary format of t = (target + 1) (from high bit to low bit, e.g. in reverse order) decides where to go at each node.<br>t % 2 == 1, go right, otherwise go left<br>t = t \/ 2 or t >>= 1<\/p>\n\n\n\n<pre class=\"wp-block-preformatted\">e.g. target = 13, t = 13 + 1 = 14\nt = 14, t % 1 = 0, t \/ 2 = 7, left\nt = 7, t % 1 = 1, t \/ 2 = 3, right\nt = 3, t % 1 = 1, t \/ 2 = 1, right\n13 => right, right, left \n0\n \\\n  2\n    \\\n     6\n   \/\n13<\/pre>\n\n\n\n<p>Time complexity: Recover O(n), find O(log|target|)<br>Space complexity: O(1)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\nclass FindElements {\npublic:\n  FindElements(TreeNode* root): root_(root) {\n    recover(root, 0);\n  }\n\n  bool find(int target) {    \n    ++target;\n    stack<bool> right;\n    while (target != 1) {\n      right.push(target & 1);\n      target >>= 1;\n    }\n    \n    TreeNode* node = root_;\n    while (!right.empty() && node) {\n      node = right.top() ? node->right : node->left;\n      right.pop();\n    }\n    \n    return node;\n  }\nprivate:\n  TreeNode* root_;\n  void recover(TreeNode* root, int val) {\n    if (!root) return;\n    root->val = val;    \n    recover(root->left, val * 2 + 1);\n    recover(root->right, val * 2 + 2);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given a&nbsp;binary tree with the following rules: root.val == 0 If&nbsp;treeNode.val == x&nbsp;and&nbsp;treeNode.left != null, then&nbsp;treeNode.left.val == 2 * x + 1 If&nbsp;treeNode.val == x&nbsp;and&nbsp;treeNode.right&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[45],"tags":[39,177,180,28],"class_list":["post-5872","post","type-post","status-publish","format-standard","hentry","category-tree","tag-binary","tag-medium","tag-stack","tag-tree","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5872","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5872"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5872\/revisions"}],"predecessor-version":[{"id":5877,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5872\/revisions\/5877"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5872"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5872"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5872"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}