The height of the binary tree is less than or equal to 20
The total number of nodes is between [1, 104]
Total calls of find() is between [1, 104]
0 <= target <= 106
Solutions
Solution 1: DFS + Hash Table
First, we traverse the binary tree using DFS, restore the node values to their original values, and store all node values in a hash table. Then, when searching, we only need to check if the target value exists in the hash table.
In terms of time complexity, it takes $O(n)$ time to traverse the binary tree during initialization, and $O(1)$ time to check if the target value exists in the hash table during search. The space complexity is $O(n)$, where $n$ is the number of nodes in the binary tree.
# 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 = rightclassFindElements:def__init__(self,root:Optional[TreeNode]):defdfs(root:Optional[TreeNode]):self.s.add(root.val)ifroot.left:root.left.val=root.val*2+1dfs(root.left)ifroot.right:root.right.val=root.val*2+2dfs(root.right)root.val=0self.s=set()dfs(root)deffind(self,target:int)->bool:returntargetinself.s# Your FindElements object will be instantiated and called as such:# obj = FindElements(root)# param_1 = obj.find(target)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */typeFindElementsstruct{smap[int]bool}funcConstructor(root*TreeNode)FindElements{root.Val=0s:=map[int]bool{}vardfsfunc(*TreeNode)dfs=func(root*TreeNode){s[root.Val]=trueifroot.Left!=nil{root.Left.Val=root.Val*2+1dfs(root.Left)}ifroot.Right!=nil{root.Right.Val=root.Val*2+2dfs(root.Right)}}dfs(root)returnFindElements{s}}func(this*FindElements)Find(targetint)bool{returnthis.s[target]}/** * Your FindElements object will be instantiated and called as such: * obj := Constructor(root); * param_1 := obj.Find(target); */