LeetCode450 删除二叉搜索树中的节点

发表于 | 分类于 |
字数统计: 787 | 阅读时长 ≈ 3

链接: https://leetcode.cn/problems/delete-node-in-a-bst/

题意

给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变

解法

一开始想了很久一直想不到解题的思路
后来经过仔细分析搜索树的性质想到
如果要删除一个节点 它一定是某棵子树的根节点
左子树中所有节点小于它，同时小于所有右子树上的节点
那么可以把它的左节点或右节点都可以作为新的根节点
如果把左节点设为新的根，则需要把左节点的右节点进行处理（移到右子树中的最左边）
反之，需要把右节点的左节点进行处理（移到左子树的最右边）
写出了一串很长的代码，新定义了四个函数
重新思考后，写出了简化后的版本，细节见代码

6.2 update
305打卡计划今天出了这一题
回过头看原先的代码觉得写的过分繁琐
在题解中找到一份简洁的实现
如果当前节点是要删除的节点
在其左子树中可以找出一个最大的（也就是最右边的节点）node
右子树中的所有元素一定都比它大
把整个右子树搬到node右边仍然满足bst的性质
再把原节点的左子节点当作新的根结点即可
但是如果要多次删除，可能会产生高度不平衡问题
but这样代码实现起来简单

代码

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
class Solution {
public:
    TreeNode* insert(TreeNode* root, TreeNode* add) {
        if (add == nullptr) return root; // 如果要插入的节点为nullptr 直接返回root
        if (root == nullptr) return add; // 如果要root为nullptr 直接返回插入节点
        if (root -> val < add -> val) { // 根据root和add的大小关系进行插入
            root -> right = insert(root -> right, add);
        }
        else {
            root -> left = insert(root -> left, add);
        }
        return root;
    }
    TreeNode* construct(TreeNode* root) {
        if (root -> left) { // 如果存在左节点 将左节点作为根节点
            TreeNode* add = root -> left -> right;
            root -> left -> right = root -> right;
            root = root -> left;
            root = insert(root, add); 
        }
        else if (root -> right){ // 如果存在右节点 将右节点作为根节点
            TreeNode* add = root -> right -> left;
            root -> right -> left = root -> left;
            root = root -> right;
            root = insert(root, add); 
        }
        else {
            root = nullptr; // 如果左右都不存在 说明树中只存在一个根节点
        }
        return root;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return root;
        if (root -> val == key) {
            return construct(root);
        }
        root -> left = deleteNode(root -> left, key);
        root -> right = deleteNode(root -> right, key);
        return root;   
    }
};

简洁版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root -> val > key) {
            root -> left = deleteNode(root -> left, key);
        }
        else if (root -> val < key) {
            root -> right = deleteNode(root -> right, key);
        }
        else {
            if (!root -> left) return root -> right;
            if (!root -> right) return root -> left;
            TreeNode* left = root -> left;
            while(left -> right) {
                left = left -> right;
            }
            left -> right = root -> right;
            root = root -> left;
        }
        return root;
    }
};