Depth First Search Algorithm with Hash Set to Find Elements in a
- Time:2020-09-10 13:27:27
- Class:Weblog
- Read:40
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.Find Elements in a Contaminated Binary Tree
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 TrueExample 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 FalseExample 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 TrueConstraints:
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^6Hints:
Use DFS to traverse the binary tree and recover it.
Use a hashset to store TreeNode.val for finding.
Depth First Search Algorithm with Hash Set
We use DFS (Depth First Search) Algorithm to traverse the binary tree while we use a hash set to remember the numbers for the recovered nodes. In C++, we use unordered_set to create a hash set.
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 33 34 | /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class FindElements { public: FindElements(TreeNode* root) { dfs(root, 0); } bool find(int target) { return data.count(target); } private: unordered_set<int> data; void dfs(TreeNode* root, int num) { if (!root) return; root-&t;val = num; data.insert(num); dfs(root->left, num * 2 + 1); dfs(root->right, num * 2 + 2); } }; /** * Your FindElements object will be instantiated and called as such: * FindElements* obj = new FindElements(root); * bool param_1 = obj->find(target); */ |
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class FindElements { public: FindElements(TreeNode* root) { dfs(root, 0); } bool find(int target) { return data.count(target); } private: unordered_set<int> data; void dfs(TreeNode* root, int num) { if (!root) return; root-&t;val = num; data.insert(num); dfs(root->left, num * 2 + 1); dfs(root->right, num * 2 + 2); } }; /** * Your FindElements object will be instantiated and called as such: * FindElements* obj = new FindElements(root); * bool param_1 = obj->find(target); */
The DFS function takes two parameters: the current Node and the recovered number for the node. Recursively, the number is calculated for the left and right children which is passed down the binary tree.
The time complexity is O(N) and the space requirement is also O(N) where N is the number of the nodes in the binary tree.
–EOF (The Ultimate Computing & Technology Blog) —
Recommend:A Quick Guide To Creating A User Persona For Your Blog
7 Top Image Compression Plugins For Your WordPress Blog
3 Ways to Convert Blog Readers to Leads
7 Ways To Deal With AdBlock Users If You’re A Blogger
2020 Design Trends [Infographic]
8 Content Marketing Plugins You Need For Your WordPress Blog
Tips to Make Money from the Comfort of Your Own Home
5 Tips for Protecting Your Freelance Business from Liabilities
5 Easy Ways On How To Build An Authority Website
How to Protect Your WordPress Site From Hackers
- Comment list
-
- Comment add