Find Elements in a Contaminated Binary Tree LeetCode solution in Python

1
# Runtime: 227 ms (Top 13.41%) | Memory: 18.1 MB (Top 62.12%)
2
# Definition for a binary tree node.
3
# class TreeNode:
4
# def __init__(self, val=0, left=None, right=None):
5
# self.val = val
6
# self.left = left
7
# self.right = right
8
class FindElements:
9

10
    def __init__(self, root: Optional[TreeNode]):
11
        def recoverTree(root):
12
            if not root:
13
                return None
14
            self.vals.add(root.val)
15
            if root.left:
16
                root.left.val = 2 * root.val + 1
17
                recoverTree(root.left)
18
            if root.right:
19
                root.right.val = 2 * root.val + 2
20
                recoverTree(root.right)
21

22
        self.vals = set()
23
        root.val = 0
24
        recoverTree(root)
25

26
    def find(self, target: int) -> bool:
27
        return target in self.vals
28

29

30
# Your FindElements object will be instantiated and called as such:
31
# obj = FindElements(root)
32
# param_1 = obj.find(target)