在受污染的二叉树中查找元素

难度: Medium

给出一个满足下述规则的二叉树：

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) 判断目标值 target 是否存在于还原后的二叉树中并返回结果。

示例 1：

输入：
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
输出：
[null,false,true]
解释：
FindElements findElements = new FindElements([-1,null,-1]); 
findElements.find(1); // return False 
findElements.find(2); // return True

示例 2：

输入：
["FindElements","find","find","find"]
[[[-1,-1,-1,-1,-1]],[1],[3],[5]]
输出：
[null,true,true,false]
解释：
FindElements findElements = new FindElements([-1,-1,-1,-1,-1]);
findElements.find(1); // return True
findElements.find(3); // return True
findElements.find(5); // return False

示例 3：

输入：
["FindElements","find","find","find","find"]
[[[-1,null,-1,-1,null,-1]],[2],[3],[4],[5]]
输出：
[null,true,false,false,true]
解释：
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

提示：

TreeNode.val == -1
二叉树的高度不超过 20
节点的总数在 [1, 10^4] 之间
调用 find() 的总次数在 [1, 10^4] 之间
0 <= target <= 10^6

Submission

运行时间: 57 ms

内存: 19.8 MB

# 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]):
        ans = set()
        ans.add(0)
        def df(root):
            temp = root.val
            if root.left:
                root.left.val = 2 * temp + 1
                ans.add(root.left.val)
                df(root.left)
            if root.right:
                root.right.val = 2 * temp + 2
                ans.add(root.right.val)
                df(root.right)
            if not root.left and not root.right:
                ans.add(root.val)
                return
        root.val = 0
        df(root)
        self.ans = ans
    
    def find(self, target: int) -> bool:
        return target in self.ans

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

Explain

题解的核心思路是通过遍历受污染的二叉树并逐步还原其原始值。由于每个节点的值都设为-1，需要根据二叉树的特性重新计算每个节点的值。根节点设置为0，对于任何节点，如果其值为x，则其左子节点的值为2x+1，右子节点的值为2x+2。通过深度优先搜索（DFS）遍历整个树，并在遍历过程中将每个节点的值存储在一个集合中，以便后续快速查找。初始化过程中，根据题目给定的污染树的结构，重新赋予每个节点正确的值并记录到集合中。在查找函数中，直接检查目标值是否存在于这个集合中。

时间复杂度: O(n) for initialization, O(1) for each find operation

空间复杂度: O(n)

# 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]):
        # 初始化集合存储所有可能的节点值
        ans = set()
        # 根节点的值设为0
        ans.add(0)
        def df(root):
            # 计算当前节点的值
            temp = root.val
            if root.left:
                # 计算左子节点的值并递归
                root.left.val = 2 * temp + 1
                ans.add(root.left.val)
                df(root.left)
            if root.right:
                # 计算右子节点的值并递归
                root.right.val = 2 * temp + 2
                ans.add(root.right.val)
                df(root.right)
            # 如果是叶子节点，也添加到集合中
            if not root.left and not root.right:
                ans.add(root.val)
                return
        # 开始从根节点进行DFS
        root.val = 0
        df(root)
        # 将集合存储为对象的一个属性，用于快速查找
        self.ans = ans
    
    def find(self, target: int) -> bool:
        # 检查目标值是否在集合中
        return target in self.ans

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

Explore

在重设节点值的过程中，DFS算法从根节点开始，递归地向下遍历每个子节点。每个节点在递归进入时就立即设置其值，并且这个值在递归过程中不会再改变。由于每个节点只被访问一次，因此每个节点的值只会被计算和设置一次，从而确保不会有重复计算。此外，递归函数不会再次访问已经设置好值的节点，因为每次递归调用都会传递到节点的子节点，而不是已处理的父节点或兄弟节点。

HashSet被选用来存储节点值主要是因为其高效的查找性能。HashSet的平均时间复杂度为O(1)对于插入和查找操作，这是因为HashSet基于哈希表实现。相比之下，如果使用列表存储节点值，查找操作的时间复杂度将为O(n)，这在节点数量较多时会显著降低性能。使用字典虽然也可以达到O(1)的查找和插入性能，但相较于HashSet，字典会存储额外的键值对信息，这在本题中没有必要，因此HashSet是一个更为节省空间且效率高的选择。

如果二叉树非常深，使用递归的DFS确实可能导致栈溢出，因为每一层递归调用都会消耗一定的栈空间。为了优化并防止栈溢出，可以采用迭代的方式使用DFS而不是递归。这通常涉及到使用一个显式的栈来模拟递归过程。在迭代DFS中，你可以手动控制栈的推送和弹出，这有助于避免深度递归造成的栈溢出问题。此外，还可以考虑使用广度优先搜索(BFS)，它使用队列而不是栈，从而避免深度递归所带来的风险。

find函数的性能确实很大程度上依赖于HashSet的性能，尤其是其查找操作的效率。HashSet的查找操作平均时间复杂度是O(1)，但在最坏情况下，如果发生大量哈希冲突，性能可能退化到O(n)。这种情况虽然不常见，但在极端情况下（如哈希函数选取不当，或者存储大量接近哈希极限的数据时）可能发生。如果HashSet的性能成为瓶颈，可以考虑重新评估哈希函数的选择，或者使用更复杂的数据结构，如平衡二叉搜索树，这些结构虽然查找时间复杂度为O(log n)，但提供更稳定的性能。