AlgoPressAppearance
0450-删除二叉搜索树中的节点
https://leetcode.cn/problems/delete-node-in-a-bst
给定一个二叉搜索树的根节点 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, 10^4].
- -10^5 <= Node.val <= 10^5
- 节点值唯一
- root 是合法的二叉搜索树
- -10^5 <= key <= 10^5
进阶： 要求算法时间复杂度为 O(h)，h 为树的高度。
思路
二叉搜索树，左子树 < 根节点 < 右子树
删除节点分以下几种情况
- 如果节点没有子节点，则 直接删除
- 如果节点没有左子树，则 右子树提上来
- 如果节点没有右子树，则 左子树提上来
- 如果左右子树都存在，则 将左子树根节点放到右子树的最左节点下面
注意：递归每次调用 DeleteNode 返回结果
csharp
public class Solution {
public TreeNode DeleteNode(TreeNode root, int key) {
if(root == null){
return null;
}
if(root.val < key){ //右子树中
root.right = DeleteNode(root.right,key);
}
else if(root.val > key){ //左子树中
root.left = DeleteNode(root.left, key);
}
else{ //自己
if(root.left == null){
return root.right;
}
else if(root.right == null){
return root.left;
}
else{
//右子树的根节点作为新的root返回
//寻找右子树的左节点，用来挂载当前左子树
TreeNode rightNode = root.right;
TreeNode leftNode = root.left;
TreeNode rightLeaf = rightNode;
while(rightLeaf.left != null){
rightLeaf = rightLeaf.left;
}
rightLeaf.left = leftNode;
return rightNode;
}
}
return root;
}
}
复习:20220512
csharp
public class Solution {
public TreeNode DeleteNode(TreeNode root, int key) {
if(root == null){
return root;
}
if( key > root.val){
root.right = DeleteNode(root.right, key);
}
else if( key < root.val ){
root.left = DeleteNode(root.left, key);
}
else { //相等
if(root.left == null){
return root.right;
}
else if(root.right == null){
return root.left;
}
else{
TreeNode left = root.left;
TreeNode right = root.right;
TreeNode leftLeaf = right; //找到右边树的最左子节点
while(leftLeaf != null && leftLeaf.left != null){
leftLeaf = leftLeaf.left;
}
leftLeaf.left = left;
return right;
}
}
return root;
}
}