LeetCode-1261. Find Elements in a Contaminated Binary Tree

LeetCode-1261. Find Elements in a Contaminated Binary Tree

Given a binary tree with the following rules:

​​root.val == 0​​If​​treeNode.val == x​​​ and​​treeNode.left != null​​​, then​​treeNode.left.val == 2 * x + 1​​If​​treeNode.val == 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​​.

You need to first recover the binary tree and then implement the ​​FindElements​​ class:

​​FindElements(TreeNode* root)​​ Initializes the object with a contamined binary tree, you need to recover it first.​​bool find(int target)​​​ Return if the​​target​​ value exists in the recovered binary tree.

Example 1:

Input["FindElements","find","find"][[[-1,null,-1]],[1],[2]]Output[null,false,true]ExplanationFindElements findElements = new FindElements([-1,null,-1]); findElements.find(1); // return False findElements.find(2); // return True

Example 2:

Input["FindElements","find","find","find"][[[-1,-1,-1,-1,-1]],[1],[3],[5]]Output[null,true,true,false]ExplanationFindElements findElements = new FindElements([-1,-1,-1,-1,-1]);findElements.find(1); // return TruefindElements.find(3); // return TruefindElements.find(5); // return False

Example 3:

Input["FindElements","find","find","find","find"][[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]Output[null,true,false,false,true]ExplanationFindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);findElements.find(2); // return TruefindElements.find(3); // return FalsefindElements.find(4); // return FalsefindElements.find(5); // return True

Constraints:

​​TreeNode.val == -1​​The height of the binary tree is less than or equal to​​20​​The total number of nodes is between​​[1, 10^4]​​Total calls of​​find()​​​ is between​​[1, 10^4]​​​​0 <= target <= 10^6​​

题解：

class FindElements { TreeNode *T = new TreeNode(-1);public: void recover(TreeNode* root, int val) { if (root != NULL) { root->val = val; recover(root->left, 2 * val + 1); recover(root->right, 2 * val + 2); } } FindElements(TreeNode* root) { if (root != NULL) { T = root; recover(T, 0); } } bool findInTree(TreeNode* root, int target) { if (root != NULL) { if (root->val == target) { return true; } return findInTree(root->left, target) || findInTree(root->right, target); } return false; } bool find(int target) { return findInTree(T, target); }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。