給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)荣月，并保證二叉搜索樹(shù)的性質(zhì)不變管呵。返回二叉搜索樹(shù)（有可能被更新）的根節(jié)點(diǎn)的引用。
一般來(lái)說(shuō)哺窄，刪除節(jié)點(diǎn)可分為兩個(gè)步驟：
首先找到需要?jiǎng)h除的節(jié)點(diǎn)捐下；
如果找到了，刪除它堂氯。
package 遞歸;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
class DeleteNodeinaBST450 {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
return root;
}
if (root.val < key) {
root.right = deleteNode(root.right, key);
return root;
}
if (root.val == key) {
if (root.left == null && root.right == null) {
return null;
}
if (root.right == null) {
return root.left;
}
if (root.left == null) {
return root.right;
}
TreeNode successor = root.right;
while (successor.left != null) {
successor = successor.left;
}
root.right = deleteNode(root.right, successor.val);
successor.right = root.right;
successor.left = root.left;
return successor;
}
return root;
}
public static void main(String[] args) {
DeleteNodeinaBST450 so = new DeleteNodeinaBST450();
TreeNode a5 = new TreeNode(5);
TreeNode a2 = new TreeNode(2);
TreeNode a3 = new TreeNode(3);
TreeNode a4 = new TreeNode(4);
TreeNode a6 = new TreeNode(6);
TreeNode a7 = new TreeNode(7);
a5.left = a3;
a5.right = a6;
a3.left = a2;
a3.right = a4;
a6.right = a7;
TreeNode b = so.deleteNode(a5, 3);
int c = 1;
}
}
刷題進(jìn)行時(shí)-遞歸-450. 刪除二叉搜索樹(shù)中的節(jié)點(diǎn)
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
- 文/潘曉璐 我一進(jìn)店門(mén)蹲蒲，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人侵贵，你說(shuō)我怎么就攤上這事届搁。” “怎么了？”我有些...
- 文/不壞的土叔 我叫張陵卡睦，是天一觀的道長(zhǎng)宴胧。 經(jīng)常有香客問(wèn)我，道長(zhǎng)表锻，這世上最難降的妖魔是什么恕齐？ 我笑而不...
- 正文 為了忘掉前任，我火速辦了婚禮瞬逊，結(jié)果婚禮上显歧，老公的妹妹穿的比我還像新娘。我一直安慰自己确镊，他們只是感情好士骤，可當(dāng)我...
- 文/花漫 我一把揭開(kāi)白布。 她就那樣靜靜地躺著蕾域，像睡著了一般敦间。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上束铭，一...
- 那天，我揣著相機(jī)與錄音厢绝，去河邊找鬼契沫。 笑死，一個(gè)胖子當(dāng)著我的面吹牛昔汉，可吹牛的內(nèi)容都是我干的懈万。 我是一名探鬼主播，決...
- 文/蒼蘭香墨 我猛地睜開(kāi)眼靶病，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼会通！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起娄周，我...
- 序言：老撾萬(wàn)榮一對(duì)情侶失蹤涕侈，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后煤辨，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體裳涛，經(jīng)...
- 正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
- 正文 我和宋清朗相戀三年众辨，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了端三。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
- 正文 年R本政府宣布育拨，位于F島的核電站，受9級(jí)特大地震影響然痊，放射性物質(zhì)發(fā)生泄漏至朗。R本人自食惡果不足惜，卻給世界環(huán)境...
- 文/蒙蒙 一剧浸、第九天 我趴在偏房一處隱蔽的房頂上張望锹引。 院中可真熱鬧，春花似錦唆香、人聲如沸嫌变。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)腾啥。三九已至，卻和暖如春冯吓，著一層夾襖步出監(jiān)牢的瞬間倘待，已是汗流浹背。 一陣腳步聲響...
- 正文 我出身青樓失尖，卻偏偏與公主長(zhǎng)得像啊奄，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子掀潮，可洞房花燭夜當(dāng)晚...
推薦閱讀更多精彩內(nèi)容
- 問(wèn)題描述 給定一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root 和一個(gè)值 key菇夸，刪除二叉搜索樹(shù)中的 key 對(duì)應(yīng)的節(jié)點(diǎn)，并保證二...
- 450 Delete Node in a BST 刪除二叉搜索樹(shù)中的節(jié)點(diǎn) Description:Given a ...
- 鏈接：刪除二叉搜索樹(shù)中的節(jié)點(diǎn)[https://leetcode-cn.com/problems/delete-no...
- 1仪吧、題目 2庄新、分析 思路一：使用層序遍歷口芍∑老伲可以記錄下父節(jié)點(diǎn)的地址轰异。方便節(jié)點(diǎn)刪除后山憨，拼接父節(jié)點(diǎn)和子樹(shù)检激。不過(guò)要處理的特...
