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

题目描述
我们现在有一棵特殊的二叉树，它的根节点是 root，树中的每个节点值都是 0 或 1。

在初始状态下，所有节点的值都是 0。

然后我们进行一系列操作：给定一个二叉树，并实现一个 FindElements 类：

1. FindElements(TreeNode* root) 构造函数接收一个受污染的二叉树根节点，其中所有节点值都是 -1（表示污染/损坏）。我们需要先恢复这棵树：

   • 从根节点开始，将根节点的值设为 0。
   • 然后对于每个节点，如果它的值为 x，那么：
     • 它的左子节点的值应为 2*x + 1。
     • 它的右子节点的值应为 2*x + 2。
   • 递归地恢复整棵树。

2. bool find(int target) 方法需要判断在恢复后的树中，是否存在一个节点的值等于 target。

你需要实现这个类，并高效地处理多次 find 调用。

示例

受污染的树（初始）：
     -1
    /   \
  -1    -1
 /  \
-1  -1

恢复后：
      0
    /   \
   1     2
  / \
 3   4

find(1) -> 返回 true
find(5) -> 返回 false

解题过程

这个问题本质上是在一棵通过规则构建的完全二叉树中，快速判断一个数是否出现在树节点中。我们需要解决两个关键点：

1. 恢复树时记录所有出现的值，以便快速查找。
2. 如果树很大，我们不想显式恢复所有节点的值（如果树结构损坏严重，可能缺失很多节点），但题目输入是完整的树结构，只是节点值初始为 -1，所以我们必须遍历整棵树来恢复。

步骤 1：理解恢复规则
根节点值为 0，左子 = 2父 + 1，右子 = 2父 + 2。
这其实是完全二叉树的数组存储格式的下标关系：

• 在数组中，根索引 0，左子索引 1，右子索引 2，对应公式：左子 = 20+1=1，右子=20+2=2。
• 对于索引 i 的左子 = 2i+1，右子 = 2i+2。
• 所以恢复后的节点值就是这个节点在“假设树是完全二叉树”中的索引编号。

这意味着：树的结构是给定的，但只有实际存在的节点才会被赋值，不存在的子节点不会出现在树中。

步骤 2：恢复与存储方案
我们可以在构造时 DFS 遍历整棵树，给每个节点赋正确的值，并把该值存入一个哈希集合，这样 find 就是 O(1) 时间。
这是最直接的做法，时间 O(N) 恢复，O(1) 查询，N 是节点数。

但题目有个额外要求：树可能很大，多次 find 调用，我们能不能不存所有值，而是用数学方法直接判断 target 是否在树中？
我们可以尝试用 DFS 在树中“定位” target，而不需要存储所有节点值。

步骤 3：不存储所有值的查找思路
已知节点值对应完全二叉树索引，那么给定一个 target，我们可以从 target 倒推出从根到它的路径。
比如 target = 3：

• 如果 target 是奇数，它一定是某个节点的左子节点，它的父节点是 (target-1)/2。
• 如果 target 是偶数，它一定是某个节点的右子节点，它的父节点是 (target-2)/2。
  不断向上直到根节点 0，我们就得到从根到 target 的路径上每个节点的值。

然后我们按照这个路径在树中向下走，检查每一步对应的子节点是否存在。

• 例如 target=3：
  • 路径推导：3 是奇数 -> 父 (3-1)/2=1。1 是奇数 -> 父 (1-1)/2=0。从根 0 开始，看左子 (1) 是否存在，然后从节点 1 看左子 (3) 是否存在。
• 如果中间某一步节点不存在，说明 target 不在树中。

步骤 4：算法实现细节

1. 恢复树：在构造函数中，我们其实不需要真的修改树节点的值为恢复后的值，因为我们的查找是数学推导路径，不需要节点存储真实值。
   但题目要求恢复，所以我们可以：

   • DFS 恢复节点值，并用哈希集合存储出现的值（为了 find 快速），这是简单方法。
   • 或者不存集合，每次 find 用路径法查找。
     路径法优点：不需要额外空间，find 时间 O(log target)，因为每次向上除 2。

2. 路径法 find 步骤：
   a. 如果 target < 0，返回 false（因为节点值非负）。
   b. 如果 target == 0，则树必须有根节点，返回 true。
   c. 计算从 target 到根 0 的路径上各层的父节点序列，然后从根出发，按这个路径一步步走，检查子节点是否存在。

   简化：其实可以直接用一个栈存路径，然后从根向下匹配。

   更简化：我们不存路径，而是用类似二进制位的方法。先找到 target 所在的“层次路径”：

   • target 不断除以 2 得到父节点，直到 0。记录每一步是左子还是右子。
   • 但这样记录的顺序是倒着的（从 target 到根），我们需要反过来（从根到 target）。

   一个巧妙方法：

   • 从根开始，我们知道 target 的值，也知道当前节点在完全二叉树中的编号 cur（从 0 开始）。
   • 但树中节点并没有存编号，所以我们必须在恢复树时记录节点与编号的关系，或者用另一种方法：
     不依赖节点存储值，而用哈希表存储“节点指针”到“编号”的映射，这样 find 时不用再恢复。

   其实更简单：恢复树时，把每个节点的计算出来的值存入哈希集合，find 时直接查集合。这样简单直接，适合面试快速实现。

步骤 5：代码实现（哈希集合法）

class FindElements {
private:
    unordered_set<int> values;
public:
    FindElements(TreeNode* root) {
        if (!root) return;
        // 恢复树并记录值
        recover(root, 0);
    }
    
    void recover(TreeNode* node, int val) {
        if (!node) return;
        node->val = val; // 恢复节点值
        values.insert(val);
        recover(node->left, 2*val + 1);
        recover(node->right, 2*val + 2);
    }
    
    bool find(int target) {
        return values.count(target) > 0;
    }
};

时间复杂度：

• 构造函数 O(N)，N 是树节点数。
• find 操作 O(1)。

空间复杂度：O(N)。

步骤 6：路径查找法（无额外空间存储值）

我们也可以不存储值，find 时通过路径查找。

1. 从 target 向上找到根路径。
2. 从根开始，根据路径一步步走到 target 的位置，检查是否存在节点。

路径获取：
比如 target=3，路径倒着是 3(左),1(左),0。正向从根 0 走：先到左子 1，再到左子 3。
如何从 target=3 得到“左左”？

• 3 的二进制 11，去掉最高位，剩下的 1 表示路径：1 表示右，0 表示左，但需要调整。

更好方法：

• 用栈存路径方向：

stack<char> path; // 'L' 或 'R'
while (target > 0) {
    if (target % 2 == 1) { // 左子
        path.push('L');
        target = (target-1)/2;
    } else { // 右子
        path.push('R');
        target = (target-2)/2;
    }
}
// 此时 target 变为 0
// 然后从根节点 cur = root 开始
TreeNode* cur = root;
while (!path.empty()) {
    char dir = path.top(); path.pop();
    if (dir == 'L') {
        if (!cur->left) return false;
        cur = cur->left;
    } else {
        if (!cur->right) return false;
        cur = cur->right;
    }
}
return true;

这个 find 时间复杂度是 O(log target)，最坏是树高。

总结
本题的关键是认识到恢复后的节点值就是完全二叉树的索引编号，利用这个性质，可以用数学推导路径的方法高效判断 target 是否存在，而无需存储所有节点值，但为了方便，哈希集合法是最直接且满足时间要求的。