Задача: 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⃣Поиск значений: Реализуйте метод поиска, который проверяет, содержится ли целевое значение в множестве восстановленных значений.

😎 Решение:

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class FindElements {
public:
    TreeNode* root;
    unordered_set<int> values;

    FindElements(TreeNode* root) {
        this->root = root;
        root->val = 0;
        values.insert(0);
        recover(root);
    }
    
    void recover(TreeNode* node) {
        if (node->left != nullptr) {
            node->left->val = 2 * node->val + 1;
            values.insert(node->left->val);
            recover(node->left);
        }
        if (node->right != nullptr) {
            node->right->val = 2 * node->val + 2;
            values.insert(node->right->val);
            recover(node->right);
        }
    }
    
    bool find(int target) {
        return values.find(target) != values.end();
    }
};

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