Description
給定一棵 BST 的根節點以及範圍 [low, high]，修剪 BST 使得所有節點的值都在 [low, high] 範圍內。修剪後的樹仍須保持 BST 性質。
Example:
Input: root = [1,0,2], low = 1, high = 2 Output: [1,null,2]
Intuition#
利用 BST 性質：節點值太小就往右找，太大就往左找，範圍內就遞迴修剪左右子樹。
- 如果當前節點值 < low，整個左子樹都不要，答案在右子樹中
- 如果當前節點值 > high，整個右子樹都不要，答案在左子樹中
- 如果在範圍內，遞迴修剪左右子樹
Approaches#
1: 遞迴#
- 概念: 利用 BST 性質遞迴修剪，超出範圍的子樹直接跳過
- 時間複雜度:
O(n) - 空間複雜度:
O(h)，h 為樹高
class Solution {
fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
if (root == null) return null
if (root.`val` < low) return trimBST(root.right, low, high)
if (root.`val` > high) return trimBST(root.left, low, high)
root.left = trimBST(root.left, low, high)
root.right = trimBST(root.right, low, high)
return root
}
}⭐ 2: 迭代#
- 概念: 先找到根節點在範圍內，再分別處理左右子樹的越界節點
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun trimBST(root: TreeNode?, low: Int, high: Int): TreeNode? {
// 找到在範圍內的根
var node = root
while (node != null && (node.`val` < low || node.`val` > high)) {
node = if (node.`val` < low) node.right else node.left
}
// 修剪左子樹中 < low 的部分
var curr = node
while (curr != null) {
while (curr.left != null && curr.left!!.`val` < low) {
curr.left = curr.left!!.right
}
curr = curr.left
}
// 修剪右子樹中 > high 的部分
curr = node
while (curr != null) {
while (curr.right != null && curr.right!!.`val` > high) {
curr.right = curr.right!!.left
}
curr = curr.right
}
return node
}
}🔑 Takeaways#
- Pattern: BST 的修剪利用有序性質，超出範圍的節點可以直接跳到另一側子樹
- 關鍵技巧: 遞迴解法三行判斷非常簡潔：太小往右、太大往左、範圍內遞迴兩側