Сложность: medium
Максимальное дерево - это дерево, в котором каждый узел имеет значение большее, чем любое другое значение в его поддереве. Вам дан корень максимального двоичного дерева и целое число val. Как и в предыдущей задаче, данное дерево было построено из списка a (root = Construct(a)) рекурсивно с помощью следующей процедуры Construct(a): Если a пусто, верните null.
В противном случае пусть a[i] - наибольший элемент a. Создайте корневой узел со значением a[i]. Левым ребенком root будет Construct([a[0], a[1], ..., a[i - 1]]). Правым ребенком root будет Construct([a[i + 1], a[i + 2], ..., a[a.length])...., a[a.length - 1]]). Возвращаем root. Обратите внимание, что нам не было дано непосредственно a, а только корневой узел root = Construct(a). Предположим, что b - это копия a с добавленным к ней значением val. Гарантируется, что b имеет уникальные значения. Возвращаем Construct(b).
Пример:
Input: root = [5,2,4,null,1], val = 3
Output: [5,2,4,null,1,null,3]
👨💻 Алгоритм:
1⃣Поиск места вставки:
Итерируйте через дерево, начиная с корня. Найдите место для вставки нового значения val так, чтобы дерево оставалось максимальным деревом. Если значение val больше, чем значение текущего узла, создайте новый узел с val и сделайте текущий узел его левым ребенком.
2⃣Вставка нового узла:
Если значение val меньше, чем значение текущего узла, продолжайте спускаться по правому поддереву, пока не найдете место для вставки.
3⃣Создание нового дерева:
После вставки нового узла убедитесь, что дерево сохраняет свои свойства максимального дерева.
😎 Решение:
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode insertIntoMaxTree(TreeNode root, int val) {
if (root == null || val > root.val) {
TreeNode newNode = new TreeNode(val);
newNode.left = root;
return newNode;
}
root.right = insertIntoMaxTree(root.right, val);
return root;
}
}Ставь 👍 и забирай 📚 Базу знаний