东哥带你刷二叉搜索树（基操篇）
数据结构精品课 已更新到 V2.1， 手把手刷二叉树系列课程 上线。
———–
在开头先打个广告，我的 手把手刷二叉树课程 按照公式和套路讲解了 150 道二叉树题目，只需一顿饭钱，就能手把手带你刷完二叉树分类的题目，迅速掌握递归思维，让你豁然开朗。我绝对有这个信心，信不信，可以等你看完我的二叉树算法系列文章再做评判。
我们前文 东哥带你刷二叉搜索树（特性篇） 介绍了 BST 的基本特性，还利用二叉搜索树「中序遍历有序」的特性来解决了几道题目，本文来实现 BST 的基础操作：判断 BST 的合法性、增、删、查。其中「删」和「判断合法性」略微复杂。
BST 的基础操作主要依赖「左小右大」的特性，可以在二叉树中做类似二分搜索的操作，寻找一个元素的效率很高。比如下面这就是一棵合法的二叉树：
对于 BST 相关的问题，你可能会经常看到类似下面这样的代码逻辑：
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
void BST(TreeNode* root, int target) {
if (root->val == target)
// 找到目标，做点什么
if (root->val < target)
BST(root->right, target);
if (root->val > target)
BST(root->left, target);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def BST(root: TreeNode, target: int) -> None:
if root.val == target:
# 找到目标，做点什么
if root.val < target:
BST(root.right, target)
if root.val > target:
BST(root.left, target)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func BST(root *TreeNode, target int) {
if root.Val == target {
// 找到目标，做点什么
}
if root.Val < target {
BST(root.Right, target)
}
if root.Val > target {
BST(root.Left, target)
}
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var BST = function(root, target) {
if (root.val === target) {
// 找到目标，做点什么
}
if (root.val < target) {
BST(root.right, target);
}
if (root.val > target) {
BST(root.left, target);
}
};
这个代码框架其实和二叉树的遍历框架差不多，无非就是利用了 BST 左小右大的特性而已。接下来看下 BST 这种结构的基础操作是如何实现的。
一、判断 BST 的合法性
力扣第 98 题「 验证二叉搜索树」就是让你判断输入的 BST 是否合法。注意，这里是有坑的哦，按照 BST 左小右大的特性，每个节点想要判断自己是否是合法的 BST 节点，要做的事不就是比较自己和左右孩子吗？感觉应该这样写代码：
boolean isValidBST(TreeNode root) {
if (root == null) return true;
// root 的左边应该更小
if (root.left != null && root.left.val >= root.val)
return false;
// root 的右边应该更大
if (root.right != null && root.right.val <= root.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
bool isValidBST(TreeNode* root) {
if (root == nullptr) return true;
// root 的左边应该更小
if (root->left != nullptr && root->left->val >= root->val)
return false;
// root 的右边应该更大
if (root->right != nullptr && root->right->val <= root->val)
return false;
return isValidBST(root->left)
&& isValidBST(root->right);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def isValidBST(root: TreeNode) -> bool:
if root is None:
return True
# root 的左边应该更小
if root.left is not None and root.left.val >= root.val:
return False
# root 的右边应该更大
if root.right is not None and root.right.val <= root.val:
return False
return isValidBST(root.left) and isValidBST(root.right)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func isValidBST(root *TreeNode) bool {
if root == nil {
return true
}
// root 的左边应该更小
if root.Left != nil && root.Left.Val >= root.Val {
return false
}
// root 的右边应该更大
if root.Right != nil && root.Right.Val <= root.Val {
return false
}
return isValidBST(root.Left)
&& isValidBST(root.Right)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var isValidBST = function(root) {
if (root === null) return true;
// root 的左边应该更小
if (root.left !== null && root.left.val >= root.val)
return false;
// root 的右边应该更大
if (root.right !== null && root.right.val <= root.val)
return false;
return isValidBST(root.left)
&& isValidBST(root.right);
}
但是这个算法出现了错误，BST 的每个节点应该要小于右边子树的所有节点，下面这个二叉树显然不是 BST，因为节点 10 的右子树中有一个节点 6，但是我们的算法会把它判定为合法 BST：
出现问题的原因在于，对于每一个节点 root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root 的整个左子树都要小于 root.val，整个右子树都要大于 root.val。
问题是，对于某一个节点 root，他只能管得了自己的左右子节点，怎么把 root 的约束传递给左右子树呢？请看正确的代码：
boolean isValidBST(TreeNode root) {
return isValidBST(root, null, null);
}
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
boolean isValidBST(TreeNode root, TreeNode min, TreeNode max) {
// base case
if (root == null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != null && root.val <= min.val) return false;
if (max != null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
bool isValidBST(TreeNode* root) {
return isValidBST(root, nullptr, nullptr);
}
// 限定以 root 为根的子树节点必须满足 max->val > root->val > min->val
bool isValidBST(TreeNode* root, TreeNode* min, TreeNode* max) {
// base case
if (root == nullptr) return true;
// 若 root->val 不符合 max 和 min 的限制，说明不是合法 BST
if (min != nullptr && root->val <= min->val) return false;
if (max != nullptr && root->val >= max->val) return false;
// 限定左子树的最大值是 root->val，右子树的最小值是 root->val
return isValidBST(root->left, min, root)
&& isValidBST(root->right, root, max);
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def isValidBST(root: TreeNode) -> bool:
def isValidBSTHelper(root, min_node, max_node):
# base case
if not root:
return True
# 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val
if min_node and root.val <= min_node.val:
return False
if max_node and root.val >= max_node.val:
return False
# 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return (isValidBSTHelper(root.left, min_node, root)
and isValidBSTHelper(root.right, root, max_node))
return isValidBSTHelper(root, None, None)
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func isValidBST(root *TreeNode) bool {
return isValidBST(root, nil, nil)
}
// 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val
func isValidBST(root *TreeNode, min *TreeNode, max *TreeNode) bool {
// base case
if root == nil {
return true
}
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if min != nil && root.Val <= min.Val {
return false
}
if max != nil && root.Val >= max.Val {
return false
}
// 限定左子树的最大值是 root.Val，右子树的最小值是 root.Val
return isValidBST(root.Left, min, root) && isValidBST(root.Right, root, max)
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/* 限定以 root 为根的子树节点必须满足 max.val > root.val > min.val */
var isValidBST = function(root, min, max) {
// base case
if (root === null) return true;
// 若 root.val 不符合 max 和 min 的限制，说明不是合法 BST
if (min !== null && root.val <= min.val) return false;
if (max !== null && root.val >= max.val) return false;
// 限定左子树的最大值是 root.val，右子树的最小值是 root.val
return isValidBST(root.left, min, root)
&& isValidBST(root.right, root, max);
}
var isValidBST = function(root) {
return isValidBST(root, null, null);
};
👾 代码可视化动画 👾
我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。
在 BST 中搜索元素
力扣第 700 题「
二叉搜索树中的搜索」就是让你在 BST 中搜索值为 target 的节点，函数签名如下：
TreeNode searchBST(TreeNode root, int target);
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* searchBST(TreeNode* root, int target);
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def searchBST(root: TreeNode, target: int) -> TreeNode:
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func searchBST(root *TreeNode, target int) *TreeNode {
// Implementation goes here
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var searchBST = function(root, target) {
};
如果是在一棵普通的二叉树中寻找，可以这样写代码：
TreeNode searchBST(TreeNode root, int target);
if (root == null) return null;
if (root.val == target) return root;
// 当前节点没找到就递归地去左右子树寻找
TreeNode left = searchBST(root.left, target);
TreeNode right = searchBST(root.right, target);
return left != null ? left : right;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* searchBST(TreeNode* root, int target) {
if (root == nullptr) return nullptr;
if (root->val == target) return root;
// 当前节点没找到就递归地去左右子树寻找
TreeNode* left = searchBST(root->left, target);
TreeNode* right = searchBST(root->right, target);
return left != nullptr ? left : right;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def searchBST(root, target):
"""
:type root: TreeNode
:type target: int
:rtype: TreeNode
"""
if not root:
return None
if root.val == target:
return root
# 当前节点没找到就递归地去左右子树寻找
left = searchBST(root.left, target)
right = searchBST(root.right, target)
return left if left else right
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func searchBST(root *TreeNode, target int) *TreeNode {
if root == nil {
return nil
}
if root.val == target {
return root
}
// 递归寻找左右子树
left := searchBST(root.left, target)
right := searchBST(root.right, target)
// 如果左子树找到了目标节点就返回左子树，否则返回右子树
if left != nil {
return left
}
return right
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var searchBST = function(root, target) {
if (root == null) return null;
if (root.val == target) return root;
// 当前节点没找到就递归地去左右子树寻找
let left = searchBST(root.left, target);
let right = searchBST(root.right, target);
return left != null ? left : right;
};
这样写完全正确，但这段代码相当于穷举了所有节点，适用于所有二叉树。那么应该如何充分利用 BST 的特殊性，把「左小右大」的特性用上？
很简单，其实不需要递归地搜索两边，类似二分查找思想，根据 target 和 root.val 的大小比较，就能排除一边。我们把上面的思路稍稍改动：
TreeNode searchBST(TreeNode root, int target) {
if (root == null) {
return null;
}
// 去左子树搜索
if (root.val > target) {
return searchBST(root.left, target);
}
// 去右子树搜索
if (root.val < target) {
return searchBST(root.right, target);
}
return root;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* searchBST(TreeNode* root, int target) {
if (root == nullptr) {
return nullptr;
}
// 去左子树搜索
if (root->val > target) {
return searchBST(root->left, target);
}
// 去右子树搜索
if (root->val < target) {
return searchBST(root->right, target);
}
return root;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def searchBST(root: TreeNode, target: int) -> TreeNode:
# 如果二叉树为空，直接返回
if not root:
return None
# 去左子树搜索
if root.val > target:
return searchBST(root.left, target)
# 去右子树搜索
if root.val < target:
return searchBST(root.right, target)
# 找到目标节点，直接返回
return root
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func searchBST(root *TreeNode, target int) *TreeNode {
if root == nil { // 如果根节点为空，返回空
return nil
}
// 去左子树搜索
if root.val > target {
return searchBST(root.left, target)
}
// 去右子树搜索
if root.val < target {
return searchBST(root.right, target)
}
// 目标值等于当前节点，直接返回
return root
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var searchBST = function(root,target) {
if (root === null) {
return null;
}
// 去左子树搜索
if (root.val > target) {
return searchBST(root.left, target);
}
// 去右子树搜索
if (root.val < target) {
return searchBST(root.right, target);
}
return root;
}
🥳 代码可视化动画 🥳
在 BST 中插入一个数
对数据结构的操作无非遍历 + 访问，遍历就是「找」，访问就是「改」。具体到这个问题，插入一个数，就是先找到插入位置，然后进行插入操作。
上一个问题，我们总结了 BST 中的遍历框架，就是「找」的问题。直接套框架，加上「改」的操作即可。一旦涉及「改」，就类似二叉树的构造问题，函数要返回 TreeNode 类型，并且要对递归调用的返回值进行接收。
TreeNode insertIntoBST(TreeNode root, int val) {
// 找到空位置插入新节点
if (root == null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 找到空位置插入新节点
if (root == nullptr) return new TreeNode(val);
// if (root->val == val)
// BST 中一般不会插入已存在元素
if (root->val < val)
root->right = insertIntoBST(root->right, val);
if (root->val > val)
root->left = insertIntoBST(root->left, val);
return root;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def insertIntoBST(root: TreeNode, val: int) -> TreeNode:
# 找到空位置插入新节点
if not root:
return TreeNode(val)
# if (root.val == val)
# BST 中一般不会插入已存在元素
if root.val < val:
root.right = insertIntoBST(root.right, val)
if root.val > val:
root.left = insertIntoBST(root.left, val)
return root
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func insertIntoBST(root *TreeNode, val int) *TreeNode {
//找到空位置插入新节点
if root == nil {
return &TreeNode{Val: val}
}
// if (root.val == val)
// 在BST中一般不会插入已存在元素
if root.Val < val {
root.Right = insertIntoBST(root.Right, val)
}
if root.Val > val {
root.Left = insertIntoBST(root.Left, val)
}
return root
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var insertIntoBST = function(root, val) {
// 找到空位置插入新节点
if (root === null) return new TreeNode(val);
// if (root.val == val)
// BST 中一般不会插入已存在元素
if (root.val < val)
root.right = insertIntoBST(root.right, val);
if (root.val > val)
root.left = insertIntoBST(root.left, val);
return root;
}
👾 代码可视化动画 👾
三、在 BST 中删除一个数
这个问题稍微复杂，跟插入操作类似，先「找」再「改」，先把框架写出来再说：
TreeNode deleteNode(TreeNode root, int key) {
if (root.val == key) {
// 找到啦，进行删除
} else if (root.val > key) {
// 去左子树找
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// 去右子树找
root.right = deleteNode(root.right, key);
}
return root;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
TreeNode* deleteNode(TreeNode* root, int key) {
if (root->val == key) {
// 找到啦，进行删除
} else if (root->val > key) {
// 去左子树找
root->left = deleteNode(root->left, key);
} else if (root->val < key) {
// 去右子树找
root->right = deleteNode(root->right, key);
}
return root;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
def deleteNode(root: TreeNode, key: int) -> TreeNode:
if root.val == key:
# 找到啦，进行删除
elif root.val > key:
# 去左子树找
root.left = deleteNode(root.left, key)
elif root.val < key:
# 去右子树找
root.right = deleteNode(root.right, key)
return root
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
func deleteNode(root *TreeNode, key int) *TreeNode {
if root.Val == key {
// 找到啦，进行删除
} else if root.Val > key {
// 去左子树找
root.Left = deleteNode(root.Left, key)
} else if root.Val < key {
// 去右子树找
root.Right = deleteNode(root.Right, key)
}
return root
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
var deleteNode = function(root, key) {
if (root.val === key) {
//找到啦， 进行删除
} else if (root.val>key) {
//去左子树找
root.left = deleteNode(root.left, key);
} else if (root.val<key) {
//去右子树找
root.right = deleteNode(root.right, key);
}
return root;
}
找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。
情况 1：A 恰好是末端节点，两个子节点都为空，那么它可以当场去世了。
if (root.left == null && root.right == null)
return null;
情况 2：A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。
// 排除了情况 1 之后
if (root.left == null) return root.right;
if (root.right == null) return root.left;
情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。
if (root.left != null && root.right != null) {
// 找到右子树的最小节点
TreeNode minNode = getMin(root.right);
// 把 root 改成 minNode
root.val = minNode.val;
// 转而去删除 minNode
root.right = deleteNode(root.right, minNode.val);
}
三种情况分析完毕，填入框架，简化一下代码：
TreeNode deleteNode(TreeNode root, int key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
TreeNode getMin(TreeNode node) {
// BST 最左边的就是最小的
while (node.left != null) node = node.left;
return node;
}
// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 在 BST 中删除节点
TreeNode deleteNode(TreeNode root, int key) {
// 当根节点为空，则直接返回 null
if (root == null) return null;
if (root.val == key) {
// 当节点为叶子节点或者只有一个子节点时，直接返回该子节点
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 当节点有两个子节点时，用其右子树最小的节点代替该节点
TreeNode minNode = getMin(root.right);
root.right = deleteNode(root.right, minNode.val);
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val > key) {
// 删除节点在左子树中
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
// 删除节点在右子树中
root.right = deleteNode(root.right, key);
}
return root;
}
// 获取以 node 为根节点的 BST 中最小的节点
TreeNode getMin(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
from typing import Optional
def deleteNode(root: Optional[TreeNode], key: int) -> Optional[TreeNode]:
if root == None:
return None
if root.val == key:
# 这两个 if 把情况 1 和 2 都正确处理了
if root.left == None:
return root.right
if root.right == None:
return root.left
# 处理情况 3
# 获得右子树最小的节点
minNode = getMin(root.right)
# 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val)
# 用右子树最小的节点替换 root 节点
minNode.left = root.left
minNode.right = root.right
root = minNode
elif root.val > key:
root.left = deleteNode(root.left, key)
elif root.val < key:
root.right = deleteNode(root.right, key)
return root
def getMin(node: Optional[TreeNode]) -> Optional[TreeNode]:
# BST 最左边的就是最小的
while node.left != None:
node = node.left
return node
// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
// 删除二叉搜索树中的一个节点
func deleteNode(root *TreeNode, key int) *TreeNode {
if root == nil {
return nil
}
if root.Val == key {
// These two if statements correctly handle cases 1 and 2
if root.Left == nil {
return root.Right
}
if root.Right == nil {
return root.Left
}
// Handle case 3
// Get the minimum node of the right subtree
minNode := getMin(root.Right)
// Delete the minimum node of the right subtree
root.Right = deleteNode(root.Right, minNode.Val)
// Replace the root node with the minimum node of the right subtree
minNode.Left = root.Left
minNode.Right = root.Right
root = minNode
} else if root.Val > key {
root.Left = deleteNode(root.Left, key)
} else if root.Val < key {
root.Right = deleteNode(root.Right, key)
}
return root
}
// Gets the minimum node of a binary search tree
func getMin(node *TreeNode) *TreeNode {
// The furthest left node of a binary search tree is the minimum node
for node.Left != nil {
node = node.Left
}
return node
}
// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码还未经过力扣测试，仅供参考，如有疑惑，可以参照我写的 java 代码对比查看。
/**
* BST 节点的定义。
* 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)
* }
*/
/**
* 删除 BST 中的一个节点并返回根节点。
* @param {TreeNode} root - 二叉树的根节点。
* @param {number} key - 待删除节点的值。
* @return {TreeNode} - 删除节点后的 BST。
*/
var deleteNode = function(root, key) {
if (root == null) return null;
if (root.val == key) {
// 这两个 if 把情况 1 和 2 都正确处理了
if (root.left == null) return root.right;
if (root.right == null) return root.left;
// 处理情况 3
// 获得右子树最小的节点
let minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
} else if (root.val > key) {
root.left = deleteNode(root.left, key);
} else if (root.val < key) {
root.right = deleteNode(root.right, key);
}
return root;
}
/**
* 获得 BST 中最小的节点。
* @param {TreeNode} node - 待查找 BST。
* @return {TreeNode} - BST 中最小的节点。
*/
var getMin = function(node) {
// BST 最左边的就是最小的
while (node.left != null) node = node.left;
return node;
}
👾 代码可视化动画 👾
这样，删除操作就完成了。注意一下，上述代码在处理情况 3 时通过一系列略微复杂的链表操作交换 root 和 minNode 两个节点：
// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
minNode.left = root.left;
minNode.right = root.right;
root = minNode;
有的读者可能会疑惑，替换 root 节点为什么这么麻烦，直接改 val 字段不就行了？看起来还更简洁易懂：
// 处理情况 3
// 获得右子树最小的节点
TreeNode minNode = getMin(root.right);
// 删除右子树最小的节点
root.right = deleteNode(root.right, minNode.val);
// 用右子树最小的节点替换 root 节点
root.val = minNode.val;
仅对于这道算法题来说是可以的，但这样操作并不完美，我们一般不会通过修改节点内部的值来交换节点。因为在实际应用中，BST 节点内部的数据域是用户自定义的，可以非常复杂，而 BST 作为数据结构（一个工具人），其操作应该和内部存储的数据域解耦，所以我们更倾向于使用指针操作来交换节点，根本没必要关心内部数据。
最后总结一下吧，通过这篇文章，我们总结出了如下几个技巧：
1、如果当前节点会对下面的子节点有整体影响，可以通过辅助函数增长参数列表，借助参数传递信息。
2、在二叉树递归框架之上，扩展出一套 BST 代码框架：
void BST(TreeNode root, int target) {
if (root.val == target)
// 找到目标，做点什么
if (root.val < target)
BST(root.right, target);
if (root.val > target)
BST(root.left, target);
}
3、根据代码框架掌握了 BST 的增删查改操作。
本文就到这里，更多经典的二叉树习题以及递归思维的训练，请参见 手把手带你刷通二叉树。
＿＿＿＿＿＿＿＿＿＿＿＿＿
《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复关键词「进群」可加入算法群；回复「全家桶」可下载配套 PDF 和刷题全家桶：
共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释