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

😎 Решение:

class TreeNode {
    public $val;
    public $left;
    public $right;
    function __construct($val = 0, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }
}

class FindElements {
    private $root;
    private $values;

    function __construct($root) {
        $this->root = $root;
        $this->values = [];
        $this->root->val = 0;
        $this->values[0] = true;
        $this->recover($root);
    }
    
    function recover($node) {
        if ($node->left !== null) {
            $node->left->val = 2 * $node->val + 1;
            $this->values[$node->left->val] = true;
            $this->recover($node->left);
        }
        if ($node->right !== null) {
            $node->right->val = 2 * $node->val + 2;
            $this->values[$node->right->val] = true;
            $this->recover($node->right);
        }
    }
    
    function find($target) {
        return isset($this->values[$target]);
    }
}

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