Сложность: 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 {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
class FindElements {
private var root: TreeNode?
private var values: Set<Int>
init(_ root: TreeNode?) {
self.root = root
self.values = Set<Int>()
if let root = root {
root.val = 0
values.insert(0)
recover(root)
}
}
private func recover(_ node: TreeNode) {
if let left = node.left {
left.val = 2 * node.val + 1
values.insert(left.val)
recover(left)
}
if let right = node.right {
right.val = 2 * node.val + 2
values.insert(right.val)
recover(right)
}
}
func find(_ target: Int) -> Bool {
return values.contains(target)
}
}Ставь 👍 и забирай 📚 Базу знаний