資訊專(zhuān)欄INFORMATION COLUMN
摘要：題目要求假設(shè)有一棵二叉搜索樹(shù)，現(xiàn)在要求從二叉搜索樹(shù)中刪除指定值，使得刪除后的結(jié)果依然是一棵二叉搜索樹(shù)。思路和代碼二叉搜索樹(shù)的特點(diǎn)是，對(duì)于樹(shù)中的任何一個(gè)節(jié)點(diǎn)，一定滿(mǎn)足大于其所有左子節(jié)點(diǎn)值，小于所有其右子節(jié)點(diǎn)值。
題目要求
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).
Example:
root = [5,3,6,2,4,null,7]
key = 3
5
/
3 6
/
2 4 7
Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the following BST.
5
/
4 6
/
2 7
Another valid answer is [5,2,6,null,4,null,7].
5
/
2 6
4 7
假設(shè)有一棵二叉搜索樹(shù)，現(xiàn)在要求從二叉搜索樹(shù)中刪除指定值，使得刪除后的結(jié)果依然是一棵二叉搜索樹(shù)。
思路和代碼二叉搜索樹(shù)的特點(diǎn)是，對(duì)于樹(shù)中的任何一個(gè)節(jié)點(diǎn)，一定滿(mǎn)足大于其所有左子節(jié)點(diǎn)值，小于所有其右子節(jié)點(diǎn)值。當(dāng)刪除二叉搜索樹(shù)中的一個(gè)節(jié)點(diǎn)時(shí)，一共有三種場(chǎng)景：
該該節(jié)點(diǎn)為葉節(jié)點(diǎn)，此時(shí)無(wú)需進(jìn)行任何操作，直接刪除該節(jié)點(diǎn)即可
該節(jié)點(diǎn)只有一個(gè)子樹(shù)，則將唯一的直接子節(jié)點(diǎn)替換掉當(dāng)前的節(jié)點(diǎn)即可
該節(jié)點(diǎn)既有做左子節(jié)點(diǎn)又有右子節(jié)點(diǎn)。這時(shí)候有兩種選擇，要么選擇左子樹(shù)的最大值，要么選擇右子樹(shù)的最小值填充至當(dāng)前的節(jié)點(diǎn)，再遞歸的在子樹(shù)中刪除對(duì)應(yīng)的最大值或是最小值。
對(duì)每種情況的圖例如下：
1. 葉節(jié)點(diǎn)
5
/
2 6
4 7 （刪除4）
結(jié)果為：
5
/
2 6
7
2. 只有左子樹(shù)或是只有右子樹(shù)
5
/
3 6
/
2 4 7（刪除6）
結(jié)果為
5
/
3 6
/
2 4
3. 既有左子樹(shù)又有右子樹(shù)
6
/
3 7
/
2 5 8 （刪除6）
/
4
首先找到6的左子樹(shù)中的最大值為5，將5填充到6的位置
5
/
3 7
/
2 5 8 （刪除5）
/
4
接著遞歸的在左子樹(shù)中刪除5，此時(shí)5滿(mǎn)足只有一個(gè)子樹(shù)的場(chǎng)景，因此直接用子樹(shù)替換即可
5
/
3 7
/
2 4 8 （刪除5）
代碼如下：
public TreeNode deleteNode(TreeNode cur, int key) {
if(cur == null) return null;
else if(cur.val == key) {
if(cur.left != null && cur.right != null) {
TreeNode left = cur.left;
while(left.right != null) {
left = left.right;
}
cur.val = left.val;
cur.left = deleteNode(cur.left, left.val);
}else if(cur.left != null) {
return cur.left;
}else if(cur.right != null){
return cur.right;
}else {
return null;
}
}else if(cur.val > key) {
cur.left = deleteNode(cur.left, key);
}else {
cur.right = deleteNode(cur.right, key);
}
return cur;
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/74579.html
Problem Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST. Basically, the deletion can be divi...
摘要：題目意思就是要一個(gè)個(gè)的返回當(dāng)前的最小值。所以解法自然就是。我們需要找出被打亂的點(diǎn)并返回正確結(jié)果。然后將兩個(gè)不正確的點(diǎn)記錄下來(lái)，最后回原來(lái)正確的值。如果是葉子節(jié)點(diǎn)，或者只有一個(gè)子樹(shù)。思想來(lái)自于的代碼實(shí)現(xiàn)。 跳過(guò)總結(jié)請(qǐng)點(diǎn)這里：https://segmentfault.com/a/11... BST最明顯的特點(diǎn)就是root.left.val < root.val < root.right.v...
摘要：解題思路我們可以用遞歸來(lái)查找，在找到需要?jiǎng)h除的節(jié)點(diǎn)后，我們需要分情況討論節(jié)點(diǎn)是葉子節(jié)點(diǎn)，直接返回節(jié)點(diǎn)有一個(gè)孩子，直接返回孩子節(jié)點(diǎn)有兩個(gè)孩子，我們要將右子樹(shù)中最小的節(jié)點(diǎn)值賦值給根節(jié)點(diǎn)，并在右子樹(shù)中刪除掉那個(gè)最小的節(jié)點(diǎn)。 Delete Node in a BSTGiven a root node reference of a BST and a key, delete the node w...
摘要：解題思路本題需要找的是第小的節(jié)點(diǎn)值，而二叉搜索樹(shù)的中序遍歷正好是數(shù)值從小到大排序的，那么這題就和中序遍歷一個(gè)情況。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...
摘要：中序遍歷復(fù)雜度時(shí)間空間思路因?yàn)樽蠊?jié)點(diǎn)小于根節(jié)點(diǎn)小于右節(jié)點(diǎn)，二叉搜索樹(shù)的一個(gè)特性就是中序遍歷的結(jié)果就是樹(shù)內(nèi)節(jié)點(diǎn)從小到大順序輸出的結(jié)果。這里采用迭代形式，我們就可以在找到第小節(jié)點(diǎn)時(shí)馬上退出。這樣我們就可以用二叉樹(shù)搜索的方法來(lái)解決這個(gè)問(wèn)題了。 Kth Smallest Element in a BST Given a binary search tree, write a function...
閱讀 1356·2023-04-26 00:35
閱讀 2728·2023-04-25 18:32
閱讀 3379·2021-11-24 11:14
閱讀 782·2021-11-22 15:24
閱讀 1432·2021-11-18 10:07
閱讀 6561·2021-09-22 10:57
閱讀 2787·2021-09-07 09:58
閱讀 3575·2019-08-30 15:54
