Сложность: 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 {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}
class Solution {
func trimBST(_ root: TreeNode?, _ low: Int, _ high: Int) -> TreeNode? {
guard let root = root else { return nil }
if root.val > high { return trimBST(root.left, low, high) }
if root.val < low { return trimBST(root.right, low, high) }
root.left = trimBST(root.left, low, high)
root.right = trimBST(root.right, low, high)
return root
}
}Ставь 👍 и забирай 📚 Базу знаний