Depth First Search Algorithm with Hash Set to Find Elements in a
- Time:2020-09-10 13:27:27
- Class:Weblog
- Read:36
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:How to Clone an Array in Javascript?
The Concurrent Programming Language: Cind
How to Design a Design Bounded Blocking Queue in Python using Th
The Unique Permutations Algorithm with Duplicate Elements
Python Coding Reference: index() and find() for string (substrin
Walking Robot Simulation Algorithm with Obstacles Detection
The Selection Sorting Algorithm in VBScript
Find the Queens That Can Attack the King
4 Bloggers Who Were Killed Because Of Their Content
Top Mobile Technology Trends for Bloggers
- Comment list
-
- Comment add