leetcode题解450：删除BST中的结点！调整二叉树的结构最难！

一、题目内容

题目要求删除二叉搜索树（BST）中值为 key 的节点，并保证删除后二叉搜索树的性质不变。返回删除节点后的二叉搜索树的根节点的引用。一般来说，删除节点可分为两个步骤：首先找到需要删除的节点；如果找到了，删除它。

二、题目分析

（一）输入和输出

输入：二叉搜索树的根节点 root 和待删除的值 key。

输出：删除指定值节点后二叉搜索树的根节点。

（二）递归函数 deleteNode 的逻辑

基本情况：如果当前节点为空（root == NULL），说明没有找到需要删除的节点，直接返回 NULL。

如果当前节点的值等于 key（root->val == key），则需要根据当前节点的子节点情况来决定如何删除：

如果当前节点是叶子节点（root->left == NULL && root->right == NULL），直接删除当前节点并返回 NULL。
如果当前节点只有一个右子节点（root->left == NULL && root->right != NULL），删除当前节点并返回其右子节点。
如果当前节点只有一个左子节点（root->left != NULL && root->right == NULL），删除当前节点并返回其左子节点。
如果当前节点既有左子节点又有右子节点，找到当前节点右子树的最左节点（即右子树中的最小值节点），将其左子树连接到该最左节点的左子树上，然后删除当前节点并返回其右子节点。

递归逻辑：如果当前节点的值大于 key（root->val > key），则递归地在左子树中删除 key 对应的节点；如果当前节点的值小于 key（root->val < key），则递归地在右子树中删除 key 对应的节点。递归返回后，将返回的子树节点赋值给当前节点的左或右子节点。

三、解题要点

（一）二叉搜索树的定义

二叉搜索树是一种特殊的二叉树，其性质是：对于任意节点，其左子树上所有节点的值都小于该节点的值，其右子树上所有节点的值都大于该节点的值。这一性质是删除操作的基础，删除操作需要保持这一性质不变。

（二）删除操作的性质

删除操作需要保持二叉搜索树的性质不变。删除节点后，树的结构需要重新调整，以确保仍然满足二叉搜索树的性质。

（三）解题思路

1.基本情况

如果当前节点为空（root == NULL），说明没有找到需要删除的节点，直接返回 NULL。这是递归的终止条件。

2.递归逻辑

比较当前节点值与待删除值：

如果当前节点的值等于 key（root->val == key），根据当前节点的子节点情况来决定如何删除。

如果当前节点的值大于 key（root->val > key），则递归地在左子树中删除 key 对应的节点。

如果当前节点的值小于 key（root->val < key），则递归地在右子树中删除 key 对应的节点。

更新子树：递归返回后，将返回的子树节点赋值给当前节点的左或右子节点。这一步确保了递归返回后，当前节点的子树被正确更新。

3.递归返回

递归返回时，返回当前节点。这一步确保了递归调用的正确性，使得每次递归返回后，当前节点的状态被正确恢复，不会影响后续的递归调用。

四、代码解答

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {// 如果当前节点为空，直接返回 NULLif (root == NULL) return NULL;// 如果当前节点的值等于 key，根据子节点情况决定如何删除if (root->val == key) {// 如果当前节点是叶子节点，直接删除并返回 NULLif (root->left == NULL && root->right == NULL) {delete root;return NULL;}// 如果当前节点只有一个右子节点，删除当前节点并返回其右子节点else if (root->left == NULL && root->right != NULL) {TreeNode* temp = root->right;delete root;return temp;}// 如果当前节点只有一个左子节点，删除当前节点并返回其左子节点else if (root->left != NULL && root->right == NULL) {TreeNode* temp = root->left;delete root;return temp;}// 如果当前节点既有左子节点又有右子节点else {// 找到当前节点右子树的最左节点TreeNode* cur = root->right;while (cur->left != NULL) {cur = cur->left;}// 将当前节点的左子树连接到最左节点的左子树上cur->left = root->left;// 删除当前节点并返回其右子节点TreeNode* temp = root->right;delete root;return temp;}}// 如果当前节点的值大于 key，递归地在左子树中删除 key 对应的节点if (root->val > key) {root->left = deleteNode(root->left, key);}// 如果当前节点的值小于 key，递归地在右子树中删除 key 对应的节点else {root->right = deleteNode(root->right, key);}// 返回当前节点return root;}
};

五、详细注释

（一）递归函数 deleteNode

基本情况：如果当前节点为空，直接返回 NULL。

如果当前节点的值等于 key，根据当前节点的子节点情况来决定如何删除。

递归逻辑：如果当前节点的值大于 key，递归地在左子树中删除 key 对应的节点；如果当前节点的值小于 key，递归地在右子树中删除 key 对应的节点。递归返回后，将返回的子树节点赋值给当前节点的左或右子节点。

六、回溯和递归的详细解释

（一）递归

递归是一种函数调用自身的方法，用于解决复杂问题。在本题中，递归用于逐层检查每个节点，找到需要删除的节点，并根据情况调整树的结构。递归的核心思想是将问题分解为更小的子问题，通过解决子问题来解决原问题。

（二）终止条件

递归的终止条件是当前节点为空，此时直接返回 NULL。这是递归的出口，确保递归不会无限进行下去。

（三）回溯

在递归调用返回后，通过返回值恢复到当前节点的状态，确保每次递归返回后，状态正确，不会影响后续的递归调用。

在本题中，回溯的过程主要体现在以下几个方面：

递归调用的返回值：每个递归分支都会返回一个节点，这个节点可以是删除操作后的子树的根节点，也可以是 NULL。
返回值的处理：在每个递归调用返回后，当前节点会根据返回值来决定下一步的操作：
- 如果当前节点的值大于 key，将返回值赋值给当前节点的左子节点。
- 如果当前节点的值小于 key，将返回值赋值给当前节点的右子节点。

（四）递归调用的详细过程

初始调用：从根节点开始调用 deleteNode(root, key)。
递归调用：如果 root->val > key，递归调用 deleteNode(root->left, key)；如果 root->val < key，递归调用 deleteNode(root->right, key)。
终止条件：当递归调用到达一个空节点时，直接返回 NULL。
回溯过程：递归返回后，将返回的子树节点赋值给当前节点的左或右子节点。递归返回到上一层调用，继续处理上一层的节点，直到返回到根节点。