Depth First Search Algorithm with Hash Set to Find Elements in a
- 时间:2020-09-10 13:27:27
- 分类:网络文摘
- 阅读:80 次
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) —
推荐阅读:巧用份数解决问题 有趣的迷路问题 华罗庚的回归 不可微——不吃饭 “健忘”的维纳 闭门羹 比上帝还挑剔的人 无理数的由来 数学王国的巾帼英雄 从死亡线上生还的人
- 评论列表
-
- 添加评论