오염된 이진 트리에서 요소 찾기

다음 규칙이 있는 이진 트리가 주어집니다.

root.val == 0

treeNode.val == x 및 treeNode.left != null이면 treeNode.left.val == 2 * x + 1

treeNode.val == x 및 treeNode.right != null이면 treeNode.right.val == 2 * x + 2

이제 이진 트리가 오염되어 모든 treeNode.val가 -1로 변경되었습니다.
FindElements 클래스를 구현합니다.

FindElements(TreeNode* root) 오염된 이진 트리로 개체를 초기화하고 복구합니다.

bool find(int target) 복구된 이진 트리에 true 값이 존재하는 경우 target를 반환합니다.

예 1:



입력
["요소 찾기","찾기","찾기"]
[[[-1,널,-1]],[1],[2]]
산출
[널,거짓,참]
설명
FindElements findElements = new FindElements([-1,null,-1]);
findElements.find(1);//거짓 반환
findElements.find(2);//참 반환

예 2:



입력
["요소 찾기","찾기","찾기","찾기"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
산출
[널,참,참,거짓]
설명
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1);//참 반환
findElements.find(3);//참 반환
findElements.find(5);//거짓 반환

예 3:



입력
["요소 찾기","찾기","찾기","찾기","찾기"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
산출
[널,참,거짓,거짓,참]
설명
FindElements findElements = new FindElements([-1,null,-1,-1,null,-1]);
findElements.find(2);//참 반환
findElements.find(3);//거짓 반환
findElements.find(4);//거짓 반환
findElements.find(5);//참 반환

제약:

TreeNode.val == -1

이진 트리의 높이가 20보다 작거나 같습니다.

총 노드 수는 [1, 104] 사이입니다.

find()의 총 통화는 [1, 104] 사이입니다.

0 <= target <= 106

해결책:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.root = root
        self.exists = set()
        nodes = [(self.root, 0)]
        while len(nodes) > 0:
            curr, l = nodes.pop()
            if curr:
                self.exists.add(l)
                nodes.append((curr.left, 2 * l + 1))
                nodes.append((curr.right, 2 * l + 2))

    def find(self, target: int) -> bool:
        return target in self.exists

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