Given a binary tree with the following rules:
root.val == 0treeNode.val == x and treeNode.left != null, then treeNode.left.val == 2 * x + 1treeNode.val == x and treeNode.right != null, then treeNode.right.val == 2 * x + 2Now the binary tree is contaminated, which means all treeNode.val have been changed to -1.
Implement the FindElements class:
FindElements(TreeNode* root) Initializes the object with a contaminated binary tree and recovers it.bool find(int target) Returns true if the target 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 == -120[1, 104]find() is between [1, 104]0 <= target <= 106This approach involves recursively traversing the contaminated binary tree and recovering the node values as per the given rules. As we traverse the tree, we will populate a set with the recovered values to allow efficient lookup for the find function.
In this implementation, we define a TreeNode structure and a FindElements object to hold the reference to the root and an array representing the possible values.
The recoverTree function is used recursively to traverse and recover the tree by assigning node values based on the rules and storing them in the boolean array.
The findElementsFind function simply checks if the target value exists in the tree by checking its presence in the array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once to recover it.
Space Complexity: O(n) for storing the node values in a boolean array.
Utilizing a breadth-first search (BFS) strategy offers a way to recover and parse through the tree's nodes iteratively. Through this approach, we harness a queue to manage node processing, ensuring we systematically visit each node layer by layer.
This C implementation showcases the BFS strategy, using an array-based queue for managing node visits. The bfsRecover function assigns and verifies values for the binary tree nodes iteratively, keeps record in a boolean array, and the findElementsFind checks the target against this recovered array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) given each node is examined once for value set-up and recovery.
Space Complexity: O(n) due to usage of a queue to store nodes and a boolean array of node values.
| Approach | Complexity |
|---|---|
| Recursive Tree Reconstruction | Time Complexity: Space Complexity: |
| BFS Iterative Tree Recovery | Time Complexity: Space Complexity: |
Find Elements in a Contaminated Binary Tree | BFS | DFS | Leetcode 1261 | codestorywithMIK • codestorywithMIK • 5,674 views views
Watch 9 more video solutions →Practice Find Elements in a Contaminated Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor