Delete Node In a BST

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

分析

节点为叶子节点：
- 如果删除的节点没有子节点，直接将其置为 nullptr
节点只有一个子节点：如果删除的节点只有左子树或右子树，则将左子树或右子树上提
节点有两个子节点：
- 在这种情况下，删除节点无法直接处理。需要找到节点的后继节点（右子树中最小的节点）
- 找到右子树中的最小节点，将其值赋给当前删除节点，然后递归删除该后继节点（变为第二种情况）

时间复杂度

最坏情况下，树的高度为 O(h)，需要进行递归查找和删除节点操作，因此时间复杂度为 O(h)

对于平衡的二叉搜索树，时间复杂度为 O(log n)；对于退化为链表的情况，时间复杂度为 O(n)

空间复杂度

递归栈的空间复杂度为 O(h)，其中 h 是树的高度。对于平衡二叉搜索树，空间复杂度为 O(log n)；对于退化为链表的情况，空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


class Solution {
public:

    // 主函数，调用删除逻辑并返回根节点
    TreeNode* deleteNode(TreeNode* root, int key)
    {
      del(root, key);  // 调用删除操作
      return root;     // 返回更新后的根节点
    }

    // 辅助函数：递归删除节点
    void del(TreeNode* &root, int key)
    {
      if (!root)  // 如果节点为空，直接返回
        return;

      // 根据 key 和当前节点值的大小关系决定递归方向
      if (root->val > key)
        del(root->left, key);  // 在左子树中查找
      else if (root->val < key)
        del(root->right, key); // 在右子树中查找
      else  // 找到目标节点
      {
        // 情况 1：节点没有子节点，直接删除
        if (!root->left && !root->right)
          root = nullptr;

        // 情况 2：节点只有右子树
        else if (!root->left)
          root = root->right;

        // 情况 3：节点只有左子树
        else if (!root->right)
          root = root->left;

        // 情况 4：节点有两个子树
        else
        {
          // 找右子树中最小的节点（后继节点）
          TreeNode* p = root->right;
          while (p->left)
            p = p->left;

          // 将后继节点的值赋给当前节点
          root->val = p->val;

          // 删除后继节点
          del(root->right, p->val);
        }
      }
    }
};