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

解题思路

本题的核心思路是先恢复二叉树的值，然后通过哈希表存储所有节点值来支持快速查找。

解法一：DFS恢复 + 哈希表存储（推荐）

根据题目给定的规则，我们可以通过深度优先搜索（DFS）来恢复二叉树：

  • 根节点值为 0
  • 对于值为 x 的节点，其左子节点值为 2x+1，右子节点值为 2x+2

在恢复过程中，我们使用哈希表（HashSet）存储所有恢复后的节点值。这样在查找时只需要 O(1) 的时间复杂度。

解法二：直接计算路径

另一种思路是不预先恢复整棵树，而是在查找时直接计算目标值在树中的路径。通过将目标值转换为二进制，可以确定从根到该节点的路径（0表示左子树，1表示右子树）。但这种方法需要每次查找都遍历路径，效率较低。

考虑到查找操作可能很频繁，推荐使用第一种解法，通过预处理和哈希表来实现 O(1) 的查找时间。

代码实现

class FindElements {
private:
    unordered_set<int> values;
    
    void dfs(TreeNode* node, int val) {
        if (!node) return;
        
        node->val = val;
        values.insert(val);
        
        dfs(node->left, 2 * val + 1);
        dfs(node->right, 2 * val + 2);
    }
    
public:
    FindElements(TreeNode* root) {
        dfs(root, 0);
    }
    
    bool find(int target) {
        return values.count(target);
    }
};

class FindElements:

    def __init__(self, root: Optional[TreeNode]):
        self.values = set()
        self.dfs(root, 0)
    
    def dfs(self, node, val):
        if not node:
            return
        
        node.val = val
        self.values.add(val)
        
        self.dfs(node.left, 2 * val + 1)
        self.dfs(node.right, 2 * val + 2)

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

public class FindElements {
    private HashSet<int> values;
    
    public FindElements(TreeNode root) {
        values = new HashSet<int>();
        Dfs(root, 0);
    }
    
    private void Dfs(TreeNode node, int val) {
        if (node == null) return;
        
        node.val = val;
        values.Add(val);
        
        Dfs(node.left, 2 * val + 1);
        Dfs(node.right, 2 * val + 2);
    }
    
    public bool Find(int target) {
        return values.Contains(target);
    }
}

var FindElements = function(root) {
    this.values = new Set();
    this.dfs(root, 0);
};

FindElements.prototype.dfs = function(node, val) {
    if (!node) return;
    
    node.val = val;
    this.values.add(val);
    
    this.dfs(node.left, 2 * val + 1);
    this.dfs(node.right, 2 * val + 2);
};

FindElements.prototype.find = function(target) {
    return this.values.has(target);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(n)O(n)
查找O(1)O(1)

其中 n 为二叉树节点数量。初始化时需要遍历所有节点进行恢复，空间复杂度主要来自哈希表存储所有节点值以及递归调用栈。