Сложность: medium
Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST.
Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям:
Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла.
Правое поддерево узла содержит только узлы с ключами, большими ключа узла.
И левое, и правое поддеревья также должны быть бинарными деревьями поиска.
Пример:
Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
👨💻 Алгоритм:
1⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево.
2⃣Посещаем текущий узел, обновляем его значение и общую сумму.
3⃣Рекурсивно обрабатываем левое поддерево.
😎 Решение:
class Solution {
private $sum = 0;
public function convertBST($root) {
if ($root !== null) {
$this->convertBST($root->right);
$this->sum += $root->val;
$root->val = $this->sum;
$this->convertBST($root->left);
}
return $root;
}
}Ставь 👍 и забирай 📚 Базу знаний