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

2022-04-03 HGNULB 约 5 分钟

文章信息 6 个分类 · 6 个标签

分类

LeetCode CodeTop 中等 未解决 1-2 字节

标签

哈希表 深度优先搜索 树 广度优先搜索 二叉树 设计

题目描述

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

题意分析

一棵二叉树的所有节点值都被污染成了负一，但左右孩子结构仍保留。需要按根值为零、值为 x 的节点左孩子为 2x + 1、右孩子为 2x + 2 的规则还原节点值。

构造对象时完成恢复，之后会多次查询某个目标值是否实际存在于树中。编号由位置决定，但树可能缺少孩子，所以不能把非负编号都当作存在，也不能仅按节点总数判断范围。

解法：DFS 复原 + 哈希集合

核心思路

[!blue]

受污染的旧数值已经不提供信息，但根的位置和左右关系足以唯一决定全部新值。从根值零开始，把当前节点应有的编号作为 DFS 参数 value 传入；写回该值，再按左右公式向存在的孩子递归。

根值正确后，只要当前节点值正确，孩子对应公式就能给出正确值，因此沿树向下可以恢复所有真实节点。缺失的孩子不会被递归，也不会加入任何不存在的编号。

恢复时同时把编号加入哈希集合。题目只查询是否存在，不要求返回路径或节点，所以集合已经保留查询所需信息。将一次遍历放在构造阶段，后面的每次 find 直接查表，避免为每个查询重新遍历树。

集合中的每个值都来自一个实际节点；每个实际节点又都从根递归到达并登记，所以集合恰好对应恢复后的节点值，成员查询与树中存在性完全一致。

解题步骤

1. 创建空集合，根非空时从编号零开始递归。
2. 将当前参数 value 写回节点，并加入集合。
3. 左孩子存在时传入 2 * value + 1，右孩子存在时传入 2 * value + 2，继续恢复。
4. 构造完成后，find(target) 直接返回集合是否包含目标。
5. 查询不再修改树或集合，重复调用彼此独立。

代码实现

class FindElements {
    private final Set<Integer> values = new HashSet<>();

    public FindElements(TreeNode root) {
        if (root != null) {
            recover(root, 0);
        }
    }

    public boolean find(int target) {
        return values.contains(target);
    }

    // value 是当前节点按位置应恢复的编号。
    private void recover(TreeNode node, int value) {
        node.val = value;
        // 集合只记录树中实际存在的节点。
        values.add(value);

        // 由正确的父值推导孩子编号，只对存在的孩子递归。
        if (node.left != null) {
            recover(node.left, value * 2 + 1);
        }

        if (node.right != null) {
            recover(node.right, value * 2 + 2);
        }
    }
}

type FindElements struct {
    values map[int]struct{}
}

func Constructor(root *TreeNode) FindElements {
    elements := FindElements{values: make(map[int]struct{})}
    if root != nil {
        elements.recover(root, 0)
    }
    return elements
}

func (elements *FindElements) Find(target int) bool {
    _, exists := elements.values[target]
    return exists
}

// value 是当前节点按位置应恢复的编号。
func (elements *FindElements) recover(node *TreeNode, value int) {
    node.Val = value
    // 集合只记录树中实际存在的节点。
    elements.values[value] = struct{}{}

    // 由正确的父值推导孩子编号，只对存在的孩子递归。
    if node.Left != nil {
        elements.recover(node.Left, value*2+1)
    }
    if node.Right != nil {
        elements.recover(node.Right, value*2+2)
    }
}

复杂度分析

• 时间复杂度：构造期望 $O(n)$，每个节点访问并入集合一次；每次查询期望 $O(1)$。若共有 q 次查询，总工作量为 $O(n+q)$。
• 空间复杂度：$O(n+h)$，集合保存 n 个编号，恢复期间递归栈深度为树高 h，整体上界为 $O(n)$。

关键点总结

[!green]

• 结构没有损坏，编号由根和左右路径推导，无需使用原来的负一值。
• 只访问真实孩子，集合自然排除稀疏树中不存在的位置。
• 构造时统一恢复与登记，将重复查询变成集合成员判断。
• 写回树值和保存查询集合是两个都需要完成的动作。

易错点总结

[!yellow]

• 左右孩子公式写反，或忘记加一、加二，会使整个子树编号错误。
• 从节点仍为负一的旧值计算孩子，而不是使用已经恢复的值或正确参数。
• 只判断目标非负或小于节点数量，稀疏树的位置编号并不连续。
• 递归一直传父节点值，没有按左右位置更新，无法恢复层次编号。
• 只往集合存正确值却不写回节点，遗漏构造函数还原树的要求。

相似题目

题目	难度	关联与区别
662. 二叉树最大宽度	中等	同样由二叉树位置生成编号，本题还可从目标编号反推根到目标的左右路径。
1104. 二叉树寻路	中等	同样查询隐式编号对应的树路径，原题编号每层反向，本题使用固定左右孩子公式。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2022/23385618

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！