BST 的删除操作及实现

# 1. 什么是BST（Binary Search Tree）

- 1.1 BST 的定义与特点
- 1.2 BST 的基本性质

# 2. BST 的节点删除操作介绍
- 2.1 BST 节点删除的原理
- 2.2 BST 节点删除的几种情况分析

# 3. 递归实现BST节点删除操作

在BST中，删除节点是一个比较复杂的操作，需要考虑到不同的情况。接下来将介绍如何使用递归实现BST节点的删除操作。

#### 3.1 递归方法概述

递归是一种常见的算法设计模式，通过在函数内部调用函数自身来解决问题。对于BST的节点删除操作，递归方法可以简化代码实现并更容易理解。

#### 3.2 递归实现BST节点删除的步骤

1. 从根节点开始递归查找要删除的节点；
2. 找到节点后，根据节点的情况进行删除操作，可能是直接删除、用左子树最大节点替换、用右子树最小节点替换等；
3. 递归调用删除函数，直到删除节点的左右子树都为空为止。

#### 3.3 递归实现BST节点删除的代码示例

下面以Python语言为例，演示递归实现BST节点删除的代码：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def deleteNode(root, key):
    if not root:
        return None
    if key < root.val:
        root.left = deleteNode(root.left, key)
    elif key > root.val:
        root.right = deleteNode(root.right, key)
    else:
        if not root.left:
            return root.right
        elif not root.right:
            return root.left
        min_node = findMin