題目描述
這是 LeetCode 上的 669. 修剪二叉搜尋樹 ,難度為 中等。
Tag : 「BST」、「二叉樹」、「遞歸」、「疊代」
給你二叉搜尋樹的根節點
root
,同時給定最小邊界
low
和最大邊界
high
。通過修剪二叉搜尋樹,使得所有節點的值在
是以結果應當傳回修剪好的二叉搜尋樹的新的根節點。注意,根節點可能會根據給定的邊界發生改變。
示例 1:
輸入:root = [1,0,2], low = 1, high = 2
輸出:[1,null,2]
示例 2:
輸入:root = [3,0,4,null,2,null,null,1], low = 1, high = 3
輸出:[3,2,null,1]
提示:
- 樹中節點數在範圍
- 樹中每個節點的值都是 唯一 的
- 題目資料保證輸入是一棵有效的二叉搜尋樹
遞歸
由于被修剪的是二叉搜尋樹,是以修剪過程必然能夠順利進行。
容易想到使用原函數作為遞歸函數:
- 若
小于邊界值root.val
,則low
的左子樹必然均小于邊界值,我們遞歸處理root
即可;root.right
- 若
大于邊界值root.val
,則high
的右子樹必然均大于邊界值,我們遞歸處理root
即可;root.left
- 若
符合要求,則root.val
可被保留,遞歸處理其左右節點并重新指派即可。root
Java 代碼:
class Solution {
public TreeNode trimBST(TreeNode root, int low, int {
if (root == null) return null;
if (root.val < low) return trimBST(root.right, low, high);
else 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
TypeScript 代碼:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
if (root == null) return null
if (root.val < low) return trimBST(root.right, low, high)
else 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
進行出發,找到第一個滿足值符合 範圍的節點,該節點為最後要傳回的根節點
ans
。
随後考慮如何修剪
ans
的左右節點:當根節點符合 要求時,修剪左右節點過程中僅需考慮一邊的邊界值即可。即對于
ans.left
隻需考慮将值小于
low
的節點去掉(因為二叉搜尋樹的特性,
ans
滿足不大于
high
要求,則其左節點必然滿足);同理
ans.right
隻需要考慮将大于
high
的節點去掉即可。
Java 代碼:
class Solution {
public TreeNode trimBST(TreeNode root, int low, int {
while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left;
TreeNode ans = root;
while (root != null) {
while (root.left != null && root.left.val < low) root.left = root.left.right;
root = root.left;
}
root = ans;
while (root != null) {
while (root.right != null && root.right.val > high) root.right = root.right.left;
root = root.right;
}
return
TypeScript 代碼:
function trimBST(root: TreeNode | null, low: number, high: number): TreeNode | null {
while (root != null && (root.val < low || root.val > high)) root = root.val < low ? root.right : root.left
const ans = root
while (root != null) {
while (root.left != null && root.left.val < low) root.left = root.left.right
root = root.left
}
root = ans
while (root != null) {
while (root.right != null && root.right.val > high) root.right = root.right.left
root = root.right
}
return
- 時間複雜度:
- 空間複雜度:
最後
這是我們「刷穿 LeetCode」系列文章的第
No.669
篇,系列開始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道題目,部分是有鎖題,我們将先把所有不帶鎖的題目刷完。
在這個系列文章裡面,除了講解解題思路以外,還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。