LeetCode 1261: Find Elements in a Contaminated Binary Tree
LeetCode 1261 Solution Explanation
Explanation:
- We are given a contaminated binary tree where each node's value has been changed to -1.
- The original binary tree followed a specific rule for values: root.val = 0, left child's value = 2 * parent's value + 1, right child's value = 2 * parent's value + 2.
- We need to implement a class that can recover the original binary tree and check if a given value exists in the recovered tree.
Algorithm:
- Initialize the root with value 0, and recursively recover the left and right subtrees.
- Use a set to store all values in the recovered tree.
- For the
findfunction, simply check if the target value exists in the set.
Time Complexity:
- Initialization: O(n) where n is the number of nodes
- Finding: O(1)
Space Complexity:
- Initialization: O(n) where n is the number of nodes
- Finding: O(1)
:
LeetCode 1261 Solutions in Java, C++, Python
import java.util.HashSet;
import java.util.Set;
class FindElements {
private Set<Integer> values;
public FindElements(TreeNode root) {
values = new HashSet<>();
recover(root, 0);
}
private void recover(TreeNode node, int val) {
if (node == null) return;
node.val = val;
values.add(val);
recover(node.left, 2 * val + 1);
recover(node.right, 2 * val + 2);
}
public boolean find(int target) {
return values.contains(target);
}
}Interactive Code Editor for LeetCode 1261
Improve Your LeetCode 1261 Solution
Use the editor below to refine the provided solution for LeetCode 1261. Select a programming language and try the following:
- Add import statements if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.
Loading editor...