# 450.删除二叉搜索树中的节点

<https://leetcode-cn.com/problems/delete-node-in-a-bst/>

### 一、递归遍历

删除一个节点A，有三种情况

**情况 1**：`A`恰好是末端节点，两个子节点都为空，直接干掉即可

**情况 2**：`A`只有一个非空子节点，那么它要让这个孩子接替自己的位置。

**情况 3**：`A`有两个子节点，较为麻烦，为了不破坏 BST 的性质，`A`必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。此处选择找右子树最小

![](/files/188rWtQDFLTzAsm6lztr)

```python
class Solution:
    def deleteNode(self, root, key: int) :
        #辅助函数，找以root为根的最小节点（即最左）
        def getMin(root):
            while root.left:
                root = root.left
            return root
        
        if root == None:
            return
        if key < root.val:
            root.left = self.deleteNode(root.left, key)
        elif key > root.val:
            root.right = self.deleteNode(root.right, key)
        else:
            if root.left == None:
                return root.right
            elif root.right == None:
                return root.left
            #左右子都不为空
            minNode = getMin(root.right)    #找右子树中最小节点
            root.val = minNode.val  #将最小节点的值移到root处
            root.right = self.deleteNode(root.right, minNode.val)   #删除最小节点

        return root
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cai-sen-se.gitbook.io/leetcode/401-600/450.-shan-chu-er-cha-sou-suo-shu-zhong-de-jie-dian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.