一、題目大意
給定一個二叉搜索樹的根節點 root 和一個值 key，洗掉二叉搜索樹中的 key 對應的節點，并保證二叉搜索樹的性質不變，回傳二叉搜索樹（有可能被更新）的根節點的參考，
一般來說，洗掉節點可分為兩個步驟：
-
首先找到需要洗掉的節點；
-
如果找到了，洗掉它，
示例 1:
輸入：root = [5,3,6,2,4,null,7], key = 3
輸出：[5,4,6,2,null,null,7]
解釋：給定需要洗掉的節點值是 3，所以我們首先找到 3 這個節點，然后洗掉它，
一個正確的答案是 [5,4,6,2,null,null,7], 如下圖所示，
另一個正確答案是 [5,2,6,null,4,null,7]，
示例 2:
輸入: root = [5,3,6,2,4,null,7], key = 0
輸出: [5,3,6,2,4,null,7]
解釋: 二叉樹不包含值為 0 的節點
示例 3:
輸入: root = [], key = 0
輸出: []
提示:
-
節點數的范圍 [0, 104].
-
-105 <= Node.val <= 105
-
節點值唯一
-
root 是合法的二叉搜索樹
-
-105 <= key <= 105
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/delete-node-in-a-bst
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
二、解題思路
這道題讓我們洗掉二叉搜索樹中的一個節點，難點在于洗掉完節點并補上那個節點的位置后還應該是一棵二叉搜索樹，被洗掉掉的節點位置，不一定是由其左右節點補上，
7
/ \
4 8
/ \
2 6
\ /
3 5
上面這棵樹，如果要洗掉節點4，那么應該將節點5補到4的位置，這樣才能保證還是BST，結果是下面這棵樹
7
/ \
5 8
/ \
2 6
\
3
遞回思路：首先判斷根節點是否為空，由于BST的性質：左 < 根 < 右，使得可以快速定位到要洗掉的節點，對于當前節點值不等于key的情況，根據大小關系對其左右子節點分別呼叫遞回函式，若當前節點就是要洗掉的節點，先判斷若有一個子節點不存在，就將root指向另一個節點，如果左右節點都不存在，那么root就賦值為空了，也正確，難點就在于處理左右子節點都存在的情況，需要在右子樹找到最濉址，即右子樹中最左下方的節點，然后將該最小值賦值給root，然后再在右子樹中呼叫遞回函式來mbmw這個最小的節點，
三、解題方法
3.1 Java實作
public class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) {
return null;
}
if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
} else {
if (root.left == null || root.right == null) {
root = (root.left != null) ? root.left : root.right;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
root.val = cur.val;
root.right = deleteNode(root.right, cur.val);
}
}
return root;
}
}
四、總結小記
- 2022/10/21 腦力勞動的人更容易摸魚
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/518864.html
標籤：其他