Given a binary tree with the following rules:
root.val == 0
- If
treeNode.val == x
andtreeNode.left != null
, thentreeNode.left.val == 2 * x + 1
- If
treeNode.val == x
andtreeNode.right != null
, thentreeNode.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 thetarget
value exists in the recovered binary tree.
Example 1:
Input ["FindElements","find","find"] [[[-1,null,-1]],[1],[2]] Output
[null,false,true]
Explanation FindElements 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]
Explanation FindElements findElements = new FindElements([-1,-1,-1,-1,-1]); findElements.find(1); // return True findElements.find(3); // return True findElements.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]
Explanation FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]); findElements.find(2); // return True findElements.find(3); // return False findElements.find(4); // return False findElements.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
Solutoin 1: Recursion and HashSet
Time complexity: Recover O(n), find O(1)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// Author: Huahua class FindElements { public: FindElements(TreeNode* root) { recover(root, 0); } bool find(int target) { return s_.count(target); } private: unordered_set<int> s_; void recover(TreeNode* root, int val) { if (!root) return; root->val = val; s_.insert(val); recover(root->left, val * 2 + 1); recover(root->right, val * 2 + 2); } }; |
Solution 2: Recursion and Binary format
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.
t % 2 == 1, go right, otherwise go left
t = t / 2 or t >>= 1
1 2 3 4 5 6 7 8 9 10 11 12 |
e.g. target = 13, t = 13 + 1 = 14 t = 14, t % 1 = 0, t / 2 = 7, left t = 7, t % 1 = 1, t / 2 = 3, right t = 3, t % 1 = 1, t / 2 = 1, right 13 => right, right, left 0 \ 2 \ 6 / 13 |
Time complexity: Recover O(n), find O(log|target|)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
// Author: Huahua class FindElements { public: FindElements(TreeNode* root): root_(root) { recover(root, 0); } bool find(int target) { ++target; stack<bool> right; while (target != 1) { right.push(target & 1); target >>= 1; } TreeNode* node = root_; while (!right.empty() && node) { node = right.top() ? node->right : node->left; right.pop(); } return node; } private: TreeNode* root_; void recover(TreeNode* root, int val) { if (!root) return; root->val = val; recover(root->left, val * 2 + 1); recover(root->right, val * 2 + 2); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment