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

Categories:

题目描述
思路分析
1. 解法一：DFS 复原 + 哈希集合（推荐）
相似题目

题目描述

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

思路分析

解法一：DFS 复原 + 哈希集合（推荐）

核心思路：

根节点赋值为 0，左子节点为 2 * x + 1，右子节点为 2 * x + 2。

DFS 或 BFS 复原整棵树，同时把所有节点值放入集合。

find(target) 直接判断集合是否包含。

复杂度分析：

时间复杂度：O(n)，复原遍历一次。

空间复杂度：O(n)，存储所有节点值。

import java.util.HashSet;
import java.util.Set;

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

    public FindElements(TreeNode root) {
        recover(root, 0);
    }

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

    private void recover(TreeNode node, int val) {
        if (node == null) {
            return;
        }
        // 复原当前节点值
        node.val = val;
        values.add(val);

        recover(node.left, val * 2 + 1);
        recover(node.right, val * 2 + 2);
    }
}

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

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

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

func (fe *FindElements) recover(node *TreeNode, val int) {
    if node == nil {
        return
    }
    // 复原当前节点值
    node.Val = val
    fe.values[val] = struct{}{}

    fe.recover(node.Left, val*2+1)
    fe.recover(node.Right, val*2+2)
}

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	BFS
144. 二叉树的前序遍历	简单	DFS
404. 左叶子之和	简单	DFS
538. 把二叉搜索树转换为累加树	中等	树遍历
700. 二叉搜索树中的搜索	简单	BST

本文作者: HGNULB

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