Задача: 1261. Find Elements in a Contaminated Binary Tree
Сложность: 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) Возвращает true, если целевое значение существует в восстановленном двоичном дереве.

Пример:

Input
["FindElements","find","find"]
[[[-1,null,-1]],[1],[2]]
Output
[null,false,true]

👨‍💻 Алгоритм:

1⃣Восстановление дерева: Начните с корневого узла, установите его значение на 0. Затем рекурсивно восстановите значения для всех узлов, используя правила left.val = 2 * parent.val + 1 и right.val = 2 * parent.val + 2.

2⃣Сохранение значений: Используйте структуру данных, такую как множество (set), для хранения всех восстановленных значений узлов.

3⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений.

😎 Решение:

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

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class FindElements {
    private TreeNode root;
    private Set<Integer> values = new HashSet<>();
    
    public FindElements(TreeNode root) {
        this.root = root;
        root.val = 0;
        values.add(0);
        recover(root);
    }
    
    private void recover(TreeNode node) {
        if (node.left != null) {
            node.left.val = 2 * node.val + 1;
            values.add(node.left.val);
            recover(node.left);
        }
        if (node.right != null) {
            node.right.val = 2 * node.val + 2;
            values.add(node.right.val);
            recover(node.right);
        }
    }
    
    public boolean find(int target) {
        return values.contains(target);
    }
}

Ставь 👍 и забирай 📚 Базу знаний