东哥带你刷二叉搜索树（基操篇）

labuladong约 8030 字大约 27 分钟数据结构二叉搜索树二叉树分解问题的思路

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
450. Delete Node in a BSTopen in new window	450. 删除二叉搜索树中的节点open in new window	🟠
700. Search in a Binary Search Treeopen in new window	700. 二叉搜索树中的搜索open in new window	🟢
701. Insert into a Binary Search Treeopen in new window	701. 二叉搜索树中的插入操作open in new window	🟠
98. Validate Binary Search Treeopen in new window	98. 验证二叉搜索树open in new window	🟠

Info

在开头先打个广告，我的手把手刷二叉树课程open in new window 按照公式和套路讲解了 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 题「验证二叉搜索树open in new window」就是让你判断输入的 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 题「二叉搜索树中的搜索open in new window」就是让你在 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 的增删查改操作。

本文就到这里，更多经典的二叉树习题以及递归思维的训练，请参见手把手带你刷通二叉树open in new window。

引用本文的文章

东哥带你刷二叉搜索树（构造篇）二叉树的递归转迭代的代码框架前缀树算法模板秒杀五道算法题后序遍历的妙用

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
-	剑指 Offer 33. 二叉搜索树的后序遍历序列open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 一、判断 BST 的合法性

# 在 BST 中搜索元素

# 在 BST 中插入一个数

# 三、在 BST 中删除一个数

一、判断 BST 的合法性

在 BST 中搜索元素

在 BST 中插入一个数

三、在 BST 中删除一个数