XTAO's Tech Blog
0%

[Leetcode]450. Delete Node in a BST(C++)

发表于 更新于 分类于 评论数：
1.7k 2 分钟

题目描述

题目链接：450. Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

例子

root = [5,3,6,2,4,null,7]
key = 3

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

Another valid answer is [5,2,6,null,4,null,7].

解题思路

有关于树的问题用递归的方式都比较好解决，针对这道题我们需要删除指定节点。最简单的方法是：首先通过二叉搜索树的性质找出该节点，然后分以下情况讨论：

  • 该节点为子节点，没有任何子树，直接删除即可
  • 该节点只有一子树（左/右子树），将该节点换成不为空的子树根即可
  • 该节点有两子树，我们可以选择将该节点的值换成左子树最大值/右子树最小值，然后删除被替换的节点即可。由于左子树最大节点肯定没有右分支；右子树最小节点肯定没有左分支，所以会回到前一种情况。

代码如下：

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
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        // case 0: tree not exist, return nullptr
        if (!root) return nullptr;

        if (root->val > key) {
            // case 1: target node is smaller than root, search it on left subtree
            root->left = deleteNode(root->left, key);
        } else if (root->val < key) {
            // case 2: target node is larger than root, search it on left subtree
            root->right = deleteNode(root->right, key);
        } else {
            // case 3.1: target node is root, if one of its subtree is empty;
            // we can replace root with the other subtree's root
            if (!root->left || !root->right) {
                root = (root->left) ? root->left : root->right;
            } else {
                // case 3.2: two of its subtrees exists
                // we replace root with the smallest node of its right subtree, then delete that node
                TreeNode *target = root->right;
                while (target->left) target = target->left;
                root->val = target->val;
                root->right = deleteNode(root->right, target->val);
            }
        }
        return root;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(k) — 树最大深度

推荐文章