参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!
二叉搜索树删除节点就涉及到结构调整了
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
首先找到需要删除的节点; 如果找到了,删除它。 说明: 要求算法时间复杂度为 $O(h)$,h 为树的高度。
示例:
《代码随想录》算法视频公开课:调整二叉树的结构最难!| LeetCode:450.删除二叉搜索树中的节点,相信结合视频在看本篇题解,更有助于大家对本题的理解。
搜索树的节点删除要比节点增加复杂的多,有很多情况需要考虑,做好心理准备。
递归三部曲:
- 确定递归函数参数以及返回值
说到递归函数的返回值,在二叉树:搜索树中的插入操作中通过递归返回值来加入新节点, 这里也可以通过递归返回值删除节点。
代码如下:
TreeNode* deleteNode(TreeNode* root, int key)
- 确定终止条件
遇到空返回,其实这也说明没找到删除的节点,遍历到空节点直接返回了
if (root == nullptr) return root;
- 确定单层递归的逻辑
这里就把二叉搜索树中删除节点遇到的情况都搞清楚。
有以下五种情况:
- 第一种情况:没找到删除的节点,遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
- 第三种情况:删除节点的左孩子为空,右孩子不为空,删除节点,右孩子补位,返回右孩子为根节点
- 第四种情况:删除节点的右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
- 第五种情况:左右孩子节点都不为空,则将删除节点的左子树头结点(左孩子)放到删除节点的右子树的最左面节点的左孩子上,返回删除节点右孩子为新的根节点。
第五种情况有点难以理解,看下面动画:
动画中的二叉搜索树中,删除元素7, 那么删除节点(元素7)的左孩子就是5,删除节点(元素7)的右子树的最左面节点是元素8。
将删除节点(元素7)的左孩子放到删除节点(元素7)的右子树的最左面节点(元素8)的左孩子上,就是把5为根节点的子树移到了8的左孩子的位置。
要删除的节点(元素7)的右孩子(元素9)为新的根节点。.
这样就完成删除元素7的逻辑,最好动手画一个图,尝试删除一个节点试试。
代码如下:
if (root->val == key) {
// 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
// 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点
if (root->left == nullptr) return root->right;
// 第四种情况:其右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
else if (root->right == nullptr) return root->left;
// 第五种情况:左右孩子节点都不为空,则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
else {
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要删除的节点(root)左子树放在cur的左孩子的位置
TreeNode* tmp = root; // 把root节点保存一下,下面来删除
root = root->right; // 返回旧root的右孩子作为新root
delete tmp; // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)
return root;
}
}
这里相当于把新的节点返回给上一层,上一层就要用 root->left 或者 root->right接住,代码如下:
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
整体代码如下:(注释中:情况1,2,3,4,5和上面分析严格对应)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root; // 第一种情况:没找到删除的节点,遍历到空节点直接返回了
if (root->val == key) {
// 第二种情况:左右孩子都为空(叶子节点),直接删除节点, 返回NULL为根节点
if (root->left == nullptr && root->right == nullptr) {
///! 内存释放
delete root;
return nullptr;
}
// 第三种情况:其左孩子为空,右孩子不为空,删除节点,右孩子补位 ,返回右孩子为根节点
else if (root->left == nullptr) {
auto retNode = root->right;
///! 内存释放
delete root;
return retNode;
}
// 第四种情况:其右孩子为空,左孩子不为空,删除节点,左孩子补位,返回左孩子为根节点
else if (root->right == nullptr) {
auto retNode = root->left;
///! 内存释放
delete root;
return retNode;
}
// 第五种情况:左右孩子节点都不为空,则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
// 并返回删除节点右孩子为新的根节点。
else {
TreeNode* cur = root->right; // 找右子树最左面的节点
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要删除的节点(root)左子树放在cur的左孩子的位置
TreeNode* tmp = root; // 把root节点保存一下,下面来删除
root = root->right; // 返回旧root的右孩子作为新root
delete tmp; // 释放节点内存(这里不写也可以,但C++最好手动释放一下吧)
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
这里我在介绍一种通用的删除,普通二叉树的删除方式(没有使用搜索树的特性,遍历整棵树),用交换值的操作来删除目标节点。
代码中目标节点(要删除的节点)被操作了两次:
- 第一次是和目标节点的右子树最左面节点交换。
- 第二次直接被NULL覆盖了。
思路有点绕,感兴趣的同学可以画图自己理解一下。
代码如下:(关键部分已经注释)
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
if (root->val == key) {
if (root->right == nullptr) { // 这里第二次操作目标值:最终删除的作用
return root->left;
}
TreeNode *cur = root->right;
while (cur->left) {
cur = cur->left;
}
swap(root->val, cur->val); // 这里第一次操作目标值:交换目标值其右子树最左面节点。
}
root->left = deleteNode(root->left, key);
root->right = deleteNode(root->right, key);
return root;
}
};
这个代码是简短一些,思路也巧妙,但是不太好想,实操性不强,推荐第一种写法!
删除节点的迭代法还是复杂一些的,但其本质我在递归法里都介绍了,最关键就是删除节点的操作(动画模拟的过程)
代码如下:
class Solution {
private:
// 将目标节点(删除节点)的左子树放到 目标节点的右子树的最左面节点的左孩子位置上
// 并返回目标节点右孩子为新的根节点
// 是动画里模拟的过程
TreeNode* deleteOneNode(TreeNode* target) {
if (target == nullptr) return target;
if (target->right == nullptr) return target->left;
TreeNode* cur = target->right;
while (cur->left) {
cur = cur->left;
}
cur->left = target->left;
return target->right;
}
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root;
TreeNode* cur = root;
TreeNode* pre = nullptr; // 记录cur的父节点,用来删除cur
while (cur) {
if (cur->val == key) break;
pre = cur;
if (cur->val > key) cur = cur->left;
else cur = cur->right;
}
if (pre == nullptr) { // 如果搜索树只有头结点
return deleteOneNode(cur);
}
// pre 要知道是删左孩子还是右孩子
if (pre->left && pre->left->val == key) {
pre->left = deleteOneNode(cur);
}
if (pre->right && pre->right->val == key) {
pre->right = deleteOneNode(cur);
}
return root;
}
};
读完本篇,大家会发现二叉搜索树删除节点比增加节点复杂的多。
因为二叉搜索树添加节点只需要在叶子上添加就可以的,不涉及到结构的调整,而删除节点操作涉及到结构的调整。
这里我们依然使用递归函数的返回值来完成把节点从二叉树中移除的操作。
这里最关键的逻辑就是第五种情况(删除一个左右孩子都不为空的节点),这种情况一定要想清楚。
而且就算想清楚了,对应的代码也未必可以写出来,所以这道题目既考察思维逻辑,也考察代码能力。
递归中我给出了两种写法,推荐大家学会第一种(利用搜索树的特性)就可以了,第二种递归写法其实是比较绕的。
最后我也给出了相应的迭代法,就是模拟递归法中的逻辑来删除节点,但需要一个pre记录cur的父节点,方便做删除操作。
迭代法其实不太容易写出来,所以如果是初学者的话,彻底掌握第一种递归写法就够了。
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
root = delete(root,key);
return root;
}
private TreeNode delete(TreeNode root, int key) {
if (root == null) return null;
if (root.val > key) {
root.left = delete(root.left,key);
} else if (root.val < key) {
root.right = delete(root.right,key);
} else {
if (root.left == null) return root.right;
if (root.right == null) return root.left;
TreeNode tmp = root.right;
while (tmp.left != null) {
tmp = tmp.left;
}
root.val = tmp.val;
root.right = delete(root.right,tmp.val);
}
return root;
}
}
// 解法2
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return root;
if (root.val == key) {
if (root.left == null) {
return root.right;
} else if (root.right == null) {
return root.left;
} else {
TreeNode cur = root.right;
while (cur.left != null) {
cur = cur.left;
}
cur.left = root.left;
root = root.right;
return root;
}
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
}
}
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if not root : return None # 节点为空,返回
if root.val < key :
root.right = self.deleteNode(root.right, key)
elif root.val > key :
root.left = self.deleteNode(root.left, key)
else:
# 当前节点的左子树为空,返回当前的右子树
if not root.left : return root.right
# 当前节点的右子树为空,返回当前的左子树
if not root.right: return root.left
# 左右子树都不为空,找到右孩子的最左节点 记为p
node = root.right
while node.left :
node = node.left
# 将当前节点的左子树挂在p的左孩子上
node.left = root.left
# 当前节点的右子树替换掉当前节点,完成当前节点的删除
root = root.right
return root
迭代法
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
# 找到节点后分两步,1. 把节点的左子树和右子树连起来,2. 把右子树跟父节点连起来
# root is None
if not root: return root
p = root
last = None
while p:
if p.val==key:
# 1. connect left to right
# right is not None -> left is None | left is not None
if p.right:
if p.left:
node = p.right
while node.left:
node = node.left
node.left = p.left
right = p.right
else:
# right is None -> right=left
right = p.left
# 2. connect right to last
if last==None:
root = right
elif last.val>key:
last.left = right
else:
last.right = right
# 3. return
break
else:
# Update last and continue
last = p
if p.val>key:
p = p.left
else:
p = p.right
return root
// 递归版本
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if key < root.Val {
root.Left = deleteNode(root.Left, key)
return root
}
if key > root.Val {
root.Right = deleteNode(root.Right, key)
return root
}
if root.Right == nil {
return root.Left
}
if root.Left == nil{
return root.Right
}
minnode := root.Right
for minnode.Left != nil {
minnode = minnode.Left
}
root.Val = minnode.Val
root.Right = deleteNode1(root.Right)
return root
}
func deleteNode1(root *TreeNode)*TreeNode {
if root.Left == nil {
pRight := root.Right
root.Right = nil
return pRight
}
root.Left = deleteNode1(root.Left)
return root
}
// 迭代版本
func deleteOneNode(target *TreeNode) *TreeNode {
if target == nil {
return target
}
if target.Right == nil {
return target.Left
}
cur := target.Right
for cur.Left != nil {
cur = cur.Left
}
cur.Left = target.Left
return target.Right
}
func deleteNode(root *TreeNode, key int) *TreeNode {
// 特殊情况处理
if root == nil {
return root
}
cur := root
var pre *TreeNode
for cur != nil {
if cur.Val == key {
break
}
pre = cur
if cur.Val > key {
cur = cur.Left
} else {
cur = cur.Right
}
}
if pre == nil {
return deleteOneNode(cur)
}
// pre 要知道是删除左孩子还有右孩子
if pre.Left != nil && pre.Left.Val == key {
pre.Left = deleteOneNode(cur)
}
if pre.Right != nil && pre.Right.Val == key {
pre.Right = deleteOneNode(cur)
}
return root
}
递归
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} key
* @return {TreeNode}
*/
var deleteNode = function(root, key) {
if (!root) return null;
if (key > root.val) {
root.right = deleteNode(root.right, key);
return root;
} else if (key < root.val) {
root.left = deleteNode(root.left, key);
return root;
} else {
// 场景1: 该节点是叶节点
if (!root.left && !root.right) {
return null
}
// 场景2: 有一个孩子节点不存在
if (root.left && !root.right) {
return root.left;
} else if (root.right && !root.left) {
return root.right;
}
// 场景3: 左右节点都存在
const rightNode = root.right;
// 获取最小值节点
const minNode = getMinNode(rightNode);
// 将待删除节点的值替换为最小值节点值
root.val = minNode.val;
// 删除最小值节点
root.right = deleteNode(root.right, minNode.val);
return root;
}
};
function getMinNode(root) {
while (root.left) {
root = root.left;
}
return root;
}
迭代
var deleteNode = function (root, key) {
const deleteOneNode = target => {
if (!target) return target
if (!target.right) return target.left
let cur = target.right
while (cur.left) {
cur = cur.left
}
cur.left = target.left
return target.right
}
if (!root) return root
let cur = root
let pre = null
while (cur) {
if (cur.val === key) break
pre = cur
cur.val > key ? cur = cur.left : cur = cur.right
}
if (!pre) {
return deleteOneNode(cur)
}
if (pre.left && pre.left.val === key) {
pre.left = deleteOneNode(cur)
}
if (pre.right && pre.right.val === key) {
pre.right = deleteOneNode(cur)
}
return root
}
递归法:
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
if (root === null) return null;
if (root.val === key) {
if (root.left === null && root.right === null) return null;
if (root.left === null) return root.right;
if (root.right === null) return root.left;
let curNode: TreeNode = root.right;
while (curNode.left !== null) {
curNode = curNode.left;
}
curNode.left = root.left;
return root.right;
}
if (root.val > key) root.left = deleteNode(root.left, key);
if (root.val < key) root.right = deleteNode(root.right, key);
return root;
};
迭代法:
function deleteNode(root: TreeNode | null, key: number): TreeNode | null {
function removeTargetNode(root: TreeNode): TreeNode | null {
if (root.left === null && root.right === null) return null;
if (root.right === null) return root.left;
if (root.left === null) return root.right;
let curNode: TreeNode | null = root.right;
while (curNode.left !== null) {
curNode = curNode.left;
}
curNode.left = root.left;
return root.right;
}
let preNode: TreeNode | null = null,
curNode: TreeNode | null = root;
while (curNode !== null) {
if (curNode.val === key) break;
preNode = curNode;
if (curNode.val > key) {
curNode = curNode.left;
} else {
curNode = curNode.right;
}
}
if (curNode === null) return root;
if (preNode === null) {
// 删除头节点
return removeTargetNode(curNode);
}
if (preNode.val > key) {
preNode.left = removeTargetNode(curNode);
} else {
preNode.right = removeTargetNode(curNode);
}
return root;
};
object Solution {
def deleteNode(root: TreeNode, key: Int): TreeNode = {
if (root == null) return root // 第一种情况,没找到删除的节点,遍历到空节点直接返回
if (root.value == key) {
// 第二种情况: 左右孩子都为空,直接删除节点,返回null
if (root.left == null && root.right == null) return null
// 第三种情况: 左孩子为空,右孩子不为空,右孩子补位
else if (root.left == null && root.right != null) return root.right
// 第四种情况: 左孩子不为空,右孩子为空,左孩子补位
else if (root.left != null && root.right == null) return root.left
// 第五种情况: 左右孩子都不为空,将删除节点的左子树头节点(左孩子)放到
// 右子树的最左边节点的左孩子上,返回删除节点的右孩子
else {
var tmp = root.right
while (tmp.left != null) tmp = tmp.left
tmp.left = root.left
return root.right
}
}
if (root.value > key) root.left = deleteNode(root.left, key)
if (root.value < key) root.right = deleteNode(root.right, key)
root // 返回根节点,return关键字可以省略
}
}