删除二叉搜索树中的节点（ LeetCode 450 ）
一、题目描述
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
1、首先找到需要删除的节点；
2、如果找到了，删除它。
二、题目解析
三、参考代码
1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 删除二叉搜索树中的节点（ LeetCode 450 ）:https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution {
public TreeNode deleteNode(TreeNode root, int key) {
// 1、如果 root 为空，那么直接返回空
if (root == null) return null;
// 2、如果 root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
if (root.val == key) {
// 情况 1：当前节点的左子树为空，那么当前节点 root 由 root 的右子树占位就行
// 比如 key 为 7
// 6
// / \
// 2 7
// \
// 8
// 直接将以 8 作为根节点的二叉树挪到 7 的位置
// 6
// / \
// 2 8
if (root.left == null) return root.right;
// 情况 2：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
// 比如 key 为 2
// 6
// / \
// 2 7
// /
// 1
// 直接将以 1 作为根节点的二叉树挪到 2 的位置
// 6
// / \
// 1 7
if (root.right == null) return root.left;
// 情况 3：被删除节点既有左子树，又有右子树
// 比如 key 为 2
// 5
// / \
// 2 6
// / \ \
// 1 4 7
// /
// 3
// 需要找到右子树最小的值，或者左子树中最大的值
// 这里我们去找右子树最小的值，为 3
TreeNode minNodeOfRight = findMinNode(root.right);
// 找到右子树最小的值之后，修改当前节点 root 的值为右子树最小的值
root.val = minNodeOfRight.val;
// 同时，记得删除掉 root 的右子树最小的值之
// 删除操作就是以 root 作为根节点，key 为右子树最小的值进行删除
root.right = deleteNode(root.right, minNodeOfRight.val);
// 3、如果 root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找
} else if (root.val < key) {
// 在 root 的右子树中去查找并删除 key
root.right = deleteNode(root.right, key);
// 4、如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找
} else if (root.val > key) {
// 在 root 的左子树中去查找并删除 key
root.left = deleteNode(root.left, key);
}
// 最后返回需要已经删除了 key 的二叉树的根节点
return root;
}
// 通过 findMinNode ，可以找到二叉搜索树中最小的元素
private TreeNode findMinNode(TreeNode node) {
// 由于二叉搜索树，左子树所有元素的值都小于根节点的值
// 所以可以不断的查找，直到为叶子节点，那么就找到了
while (node.left != null) {
// 不断的去查找当前节点的左子树
node = node.left;
}
// 返回当前二叉搜索树中最小的元素
return node;
}
}
2、C++ 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 删除二叉搜索树中的节点（ LeetCode 450 ）:https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution
{
public:
TreeNode *deleteNode(TreeNode *root, int key)
{
// 1、如果 root 为空，那么直接返回空
if (root == NULL)
return NULL;
// 2、如果 root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
if (root->val == key)
{
// 情况 1：当前节点的左子树为空，那么当前节点 root 由 root 的右子树占位就行
// 比如 key 为 7
// 6
// / \
// 2 7
// \
// 8
// 直接将以 8 作为根节点的二叉树挪到 7 的位置
// 6
// / \
// 2 8
if (root->left == NULL)
return root->right;
// 情况 2：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
// 比如 key 为 2
// 6
// / \
// 2 7
// /
// 1
// 直接将以 1 作为根节点的二叉树挪到 2 的位置
// 6
// / \
// 1 7
if (root->right == NULL)
return root->left;
// 情况 3：被删除节点既有左子树，又有右子树
// 比如 key 为 2
// 5
// / \
// 2 6
// / \ \
// 1 4 7
// /
// 3
// 需要找到右子树最小的值，或者左子树中最大的值
// 这里我们去找右子树最小的值，为 3
TreeNode *minNodeOfRight = findMinNode(root->right);
// 找到右子树最小的值之后，修改当前节点 root 的值为右子树最小的值
root->val = minNodeOfRight->val;
// 同时，记得删除掉 root 的右子树最小的值之
// 删除操作就是以 root 作为根节点，key 为右子树最小的值进行删除
root->right = deleteNode(root->right, minNodeOfRight->val);
// 3、如果 root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找
}
else if (root->val < key)
{
// 在 root 的右子树中去查找并删除 key
root->right = deleteNode(root->right, key);
// 4、如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找
}
else if (root->val > key)
{
// 在 root 的左子树中去查找并删除 key
root->left = deleteNode(root->left, key);
}
// 最后返回需要已经删除了 key 的二叉树的根节点
return root;
}
// 通过 findMinNode ，可以找到二叉搜索树中最小的元素
TreeNode *findMinNode(TreeNode *node)
{
// 由于二叉搜索树，左子树所有元素的值都小于根节点的值
// 所以可以不断的查找，直到为叶子节点，那么就找到了
while (node->left != NULL)
{
// 不断的去查找当前节点的左子树
node = node->left;
}
// 返回当前二叉搜索树中最小的元素
return node;
}
};
3、Python 代码
# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 删除二叉搜索树中的节点（ LeetCode 450 ）:https://leetcode-cn.com/problems/delete-node-in-a-bst/
class Solution:
def deleteNode(self, root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
# 1、如果 root 为空，那么直接返回空
if not root :
return None
# 2、如果 root 的节点值等于需要删除的值，那么需要根据以下几种情况进行处理
if root.val == key :
# 情况 1：当前节点的左子树为空，那么当前节点 root 由 root 的右子树占位就行
# 比如 key 为 7
# 6
# / \
# 2 7
# \
# 8
# 直接将以 8 作为根节点的二叉树挪到 7 的位置
# 6
# / \
# 2 8
if not root.left:
return root.right
# 情况 2：当前节点的右子树为空，那么当前节点 root 由 root 的左子树占位就行
# 比如 key 为 2
# 6
# / \
# 2 7
# /
# 1
# 直接将以 1 作为根节点的二叉树挪到 2 的位置
# 6
# / \
# 1 7
if not root.right :
return root.left
# 情况 3：被删除节点既有左子树，又有右子树
# 比如 key 为 2
# 5
# / \
# 2 6
# / \ \
# 1 4 7
# /
# 3
# 需要找到右子树最小的值，或者左子树中最大的值
# 这里我们去找右子树最小的值，为 3
minNodeOfRight = self.findMinNode(root.right)
# 找到右子树最小的值之后，修改当前节点 root 的值为右子树最小的值
root.val = minNodeOfRight.val
# 同时，记得删除掉 root 的右子树最小的值之
# 删除操作就是以 root 的右子树作为根节点，key 为右子树最小的值进行删除
root.right = self.deleteNode(root.right,minNodeOfRight.val)
# 3、如果 root 的节点值小于需要删除的值，那么就在 root 的右子树中去查找
elif root.val < key :
# 在 root 的右子树中去查找并删除 key
root.right = self.deleteNode(root.right,key)
# 4、如果 root 的节点值大于需要删除的值，那么就在 root 的左子树中去查找
elif root.val > key :
# 在 root 的左子树中去查找并删除 key
root.left = self.deleteNode(root.left,key)
# 最后返回需要已经删除了 key 的二叉树的根节点
return root
# 通过 findMinNode ，可以找到二叉搜索树中最小的元素
def findMinNode(self , node : TreeNode) -> TreeNode :
# 由于二叉搜索树，左子树所有元素的值都小于根节点的值
# 所以可以不断的查找，直到为叶子节点，那么就找到了
while node.left :
# 不断的去查找当前节点的左子树
node = node.left
# 返回当前二叉搜索树中最小的元素
return node
