Сложность: medium
Дано корневое дерево двоичного поиска и нижняя и верхняя границы как low и high. Обрежьте дерево так, чтобы все его элементы лежали в диапазоне [low, high]. Обрезка дерева не должна изменять относительную структуру элементов, которые останутся в дереве (то есть любой потомок узла должен оставаться потомком). Можно доказать, что существует единственный ответ.
Верните корень обрезанного дерева двоичного поиска. Обратите внимание, что корень может измениться в зависимости от заданных границ.
Пример:
Input: root = [1,0,2], low = 1, high = 2
Output: [1,null,2]
👨💻 Алгоритм:
1⃣Если node.val > high, то обрезанное двоичное дерево должно находиться слева от узла.
2⃣Если node.val < low, то обрезанное двоичное дерево должно находиться справа от узла.
3⃣В противном случае обрезаем обе стороны дерева.
😎 Решение:
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def trimBST(self, root: TreeNode, low: int, high: int) -> TreeNode:
if not root:
return None
if root.val > high:
return self.trimBST(root.left, low, high)
if root.val < low:
return self.trimBST(root.right, low, high)
root.left = self.trimBST(root.left, low, high)
root.right = self.trimBST(root.right, low, high)
return root
Ставь 👍 и забирай 📚 Базу знаний