Сложность: 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⃣Обратный обход in-order:
Пройдите по дереву в порядке "правый, корень, левый" (обратный in-order обход). Это обеспечит посещение узлов в порядке убывания их значений.
2⃣Накопление суммы:
Во время обхода поддерживайте переменную для хранения накопленной суммы. На каждом узле добавляйте значение узла к накопленной сумме и обновляйте значение узла этой накопленной суммой.
3⃣Преобразование узлов:
Преобразуйте значение каждого узла в накопленную сумму.
😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def bstToGst(self, root: TreeNode) -> TreeNode:
self.sum = 0
def reverse_inorder(node):
if not node:
return
reverse_inorder(node.right)
self.sum += node.val
node.val = self.sum
reverse_inorder(node.left)
reverse_inorder(root)
return root
Ставь 👍 и забирай 📚 Базу знаний