669. 修剪二叉搜索樹
給定一個(gè)二叉搜索樹逆屡，同時(shí)給定最小邊界L 和最大邊界 R咖气。通過(guò)修剪二叉搜索樹睬隶，使得所有節(jié)點(diǎn)的值在[L, R]中 (R>=L) 愉烙。你可能需要改變樹的根節(jié)點(diǎn)桅打，所以結(jié)果應(yīng)當(dāng)返回修剪好的二叉搜索樹的新的根節(jié)點(diǎn)是嗜。
示例1:
輸入:
1
/ \
0 2
L = 1
R = 2
輸出:
1
\
2
示例2:
輸入:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
輸出:
3
/
2
/
1
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)挺尾，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處鹅搪。
-
創(chuàng)建二叉搜索樹
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
-
1. 遞歸法
思路：
- 判斷當(dāng)前根節(jié)點(diǎn)的值和區(qū)間的左右邊界
- 如果根節(jié)點(diǎn)的值都大于區(qū)間的右邊界，那么右子樹的值一定都大于右區(qū)間潦嘶，我們只需修剪左子樹即可, 反之同理
- 如果當(dāng)前根節(jié)點(diǎn)在區(qū)間內(nèi)涩嚣，分別修剪左右子樹即可
public TreeNode trimBST(TreeNode root, int L, int R) {
if (root == null) return null;
//如果根節(jié)點(diǎn)的值都大于區(qū)間的右邊界，那么右子樹的值一定都大于右區(qū)間掂僵，我們只需修剪左子樹即可
if (root.val > R) {
return trimBST(root.left, L, R);
}
//同理
if (root.val < L) {
return trimBST(root.right, L, R);
}
root.left = trimBST(root.left, L, R);
root.right = trimBST(root.right, L, R);
return root;
}
復(fù)雜度分析：
- 時(shí)間復(fù)雜度：O(n), 最壞情況下每個(gè)節(jié)點(diǎn)都需要訪問(wèn)一次
- 空間復(fù)雜度：O(n), 在最糟糕的情況下航厚，我們遞歸調(diào)用的棧可能與節(jié)點(diǎn)數(shù)一樣大锰蓬。
-
源碼
-
我會(huì)每天更新新的算法幔睬，并盡可能嘗試不同解法，如果發(fā)現(xiàn)問(wèn)題請(qǐng)指正
- Github
