代码随想录算法训练营第22天 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

发布于 2022-12-06  211 次阅读

AI 摘要

文章标题：代码随想录算法训练营第22天 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点 这篇文章讲解了三个有关二叉搜索树的算法题目：235. 二叉搜索树的最近公共祖先、701. 二叉搜索树中的插入操作和450. 删除二叉搜索树中的节点。对于第一个问题，作者讲解了递归和迭代两种解法，代码时间复杂度分别为O(logn)和O(n)。对于后两个问题，作者同样给出了递归和迭代两种解法，时间复杂度为O(logn)。同时，文章中还提到了标准答案，供读者参考。

235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

思路:

  • 使用递归法，先将指定值中的较小值设为lval，较大值设为rval，如果root->val >= lval && root->val <= rval，则之间返回root，否则如果root->val < lval，说明公共祖先在右子树，如果root->val > rval，说明公共祖先在左子树

我的AC代码

递归法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* findAncestor(TreeNode* root, int lval, int rval) {
        if(root == nullptr) {
            return nullptr;
        }
        if(root->val >= lval && root->val <= rval) {
            return root;
        }
        if(root->val > rval) {
            return findAncestor(root->left, lval, rval);
        }
        else if(root->val < lval){
            return findAncestor(root->right, lval, rval);
        }
        return root;
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p->val < q->val) {
            return findAncestor(root, p->val, q->val);
        }
        else {
            return findAncestor(root, q->val, p->val);
        }
    }
};

标准答案

递归法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
private:
    TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
        if (cur == NULL) return cur;
                                                        // 中
        if (cur->val > p->val && cur->val > q->val) {   // 左
            TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

        if (cur->val < p->val && cur->val < q->val) {   // 右
            TreeNode* right = traversal(cur->right, p, q);
            if (right != NULL) {
                return right;
            }
        }
        return cur;
    }
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return traversal(root, p, q);
    }
};

迭代法

//时间复杂度O(n),空间复杂度O(n)
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        while(root) {
            if (root->val > p->val && root->val > q->val) {
                root = root->left;
            } else if (root->val < p->val && root->val < q->val) {
                root = root->right;
            } else return root;
        }
        return NULL;
    }
};

701. 二叉搜索树中的插入操作 - 力扣（LeetCode）

思路:

  • 递归法，当节点为空指针时构造一个值为val的节点并且返回给上一层，上一层要指向该返回值
  • 迭代法，如果val > cur->val说明插入点在右子树中，如果此时cur->right == nullptr，说明cur->right就是插入点，否则执行cur = cur -> right;如果val < cur->val说明插入点在左子树中，如果此时cur->left == nullptr，说明cur->left就是插入点，否则执行cur = cur->left

我的AC代码

递归法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* insert(TreeNode* root, int val) {
        if(root == nullptr) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if(root->val > val) {
            root->left = insert(root->left, val);
        }
        if(root->val < val) {
            root->right = insert(root->right, val);
        }
        return root;
    }
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        return insert(root, val);
    }
};

迭代法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* tmp = new TreeNode(val);
        TreeNode* cur = root;
        if(cur == nullptr) {
            return tmp;
        }
        while(cur != nullptr) {
            if(val > cur->val) {
                if(cur->right == nullptr) {
                    cur->right = tmp;
                    return root;
                }
                else {
                    cur = cur->right;
                }
            }
            else if(val < cur->val) {
                if(cur->left == nullptr) {
                    cur->left = tmp;
                    return root;
                }
                else {
                    cur = cur->left;
                }
            }
        }
        return root;
    }
};

标准答案

递归(有返回值)

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

递归(无返回值)

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
private:
    TreeNode* parent;
    void traversal(TreeNode* cur, int val) {
        if (cur == NULL) {
            TreeNode* node = new TreeNode(val);
            if (val > parent->val) parent->right = node;
            else parent->left = node;
            return;
        }
        parent = cur;
        if (cur->val > val) traversal(cur->left, val);
        if (cur->val < val) traversal(cur->right, val);
        return;
    }

public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        parent = new TreeNode(0);
        if (root == NULL) {
            root = new TreeNode(val);
        }
        traversal(root, val);
        return root;
    }
};

迭代法

//时间复杂度O(logn),空间复杂度O(logn)
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* node = new TreeNode(val);
            return node;
        }
        TreeNode* cur = root;
        TreeNode* parent = root; // 这个很重要，需要记录上一个节点，否则无法赋值新节点
        while (cur != NULL) {
            parent = cur;
            if (cur->val > val) cur = cur->left;
            else cur = cur->right;
        }
        TreeNode* node = new TreeNode(val);
        if (val < parent->val) parent->left = node;// 此时是用parent节点的进行赋值
        else parent->right = node;
        return root;
    }
};

450. 删除二叉搜索树中的节点 - 力扣（LeetCode）

思路:

  • 我的方法：我写了一个究极究极复杂的迭代法，在找到要删除的节点的时候大体分三种情况，一种是要删除的是根节点，一种是要删除的节点是前一节点的左节点，另一种是要删除的节点是前一节点的右节点，每个情况下又分要删除的节点左右两侧是否为空，有各自情况的处理办法。如果还没找到要删除的节点，就根据大小来判断，要删除的节点的值大于当前节点，就去右子树找，否则就去左子树找，每次移动的时候要记得把前一个节点的值赋给pre

我的AC代码

//时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* cur = root;
        TreeNode* pre = cur;
        if(cur == nullptr) {
            return nullptr;
        }
        while(cur != nullptr) {
            if(cur->val == key) {
                if(cur == pre) {
                    if(cur->right == nullptr) {
                        return cur->left;
                    }
                    else if(cur->left == nullptr) {
                        return cur->right;
                    }
                    TreeNode* tmp = cur->right;
                    while(tmp->left != nullptr) {
                        tmp = tmp->left;
                    }
                    tmp->left = cur->left;
                    return cur->right;
                }
                else {
                    if(cur->val < pre->val) {
                        if(cur->right == nullptr) {
                            pre->left = cur->left;
                            return root;
                        }
                        else if(cur->right == nullptr) {
                            pre->left = cur->right;
                            return root;
                        }
                        else {
                            TreeNode* tmp = cur->right;
                            while(tmp->left != nullptr) {
                                tmp = tmp->left;
                            }
                            pre->left = cur->right;
                            tmp->left = cur->left;
                            return root;
                        }
                    }
                    else if(cur->val > pre->val) {
                        if(cur->right == nullptr) {
                            pre->right = cur->left;
                            return root;
                        }
                        else if(cur->right == nullptr) {
                            pre->right = cur->right;
                            return root;
                        }
                        else {
                            TreeNode* tmp = cur->right;
                            while(tmp->left != nullptr) {
                                tmp = tmp->left;
                            }
                            pre->right = cur->right;
                            tmp->left = cur->left;
                            return root;
                        }
                    }
                }
            }
            else if(cur->val < key) {
                pre = cur;
                cur = cur->right;
            }
            else if(cur->val > key) {
                pre = cur;
                cur = cur->left;
            }
        }
        return root;
    }
};

标准答案

递归法

//时间复杂度O(logn),空间复杂度O(1)
class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
        if (root->val == key) {
            // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
            if (root->left == nullptr && root->right == nullptr) {
                ///! 内存释放
                delete root;
                return nullptr;
            }
            // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
            else if (root->left == nullptr) {
                auto retNode = root->right;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
            else if (root->right == nullptr) {
                auto retNode = root->left;
                ///! 内存释放
                delete root;
                return retNode;
            }
            // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
            // 并返回删除节点右孩子为新的根节点。
            else {
                TreeNode* cur = root->right; // 找右子树最左面的节点
                while(cur->left != nullptr) {
                    cur = cur->left;
                }
                cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                root = root->right;     // 返回旧root的右孩子作为新root
                delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                return root;
            }
        }
        if (root->val > key) root->left = deleteNode(root->left, key);
        if (root->val < key) root->right = deleteNode(root->right, key);
        return root;
    }
};

插播(普通二叉树删除节点办法)

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        if (root->val == key) {
            if (root->right == nullptr) { // 这里第二次操作目标值：最终删除的作用
                return root->left;
            }
            TreeNode *cur = root->right;
            while (cur->left) {
                cur = cur->left;
            }
            swap(root->val, cur->val); // 这里第一次操作目标值：交换目标值其右子树最左面节点。
        }
        root->left = deleteNode(root->left, key);
        root->right = deleteNode(root->right, key);
        return root;
    }
};

迭代法

//时间复杂度O(logn),空间复杂度O(1)
class Solution {
private:
    // 将目标节点（删除节点）的左子树放到 目标节点的右子树的最左面节点的左孩子位置上
    // 并返回目标节点右孩子为新的根节点
    // 是动画里模拟的过程
    TreeNode* deleteOneNode(TreeNode* target) {
        if (target == nullptr) return target;
        if (target->right == nullptr) return target->left;
        TreeNode* cur = target->right;
        while (cur->left) {
            cur = cur->left;
        }
        cur->left = target->left;
        return target->right;
    }
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return root;
        TreeNode* cur = root;
        TreeNode* pre = nullptr; // 记录cur的父节点，用来删除cur
        while (cur) {
            if (cur->val == key) break;
            pre = cur;
            if (cur->val > key) cur = cur->left;
            else cur = cur->right;
        }
        if (pre == nullptr) { // 如果搜索树只有头结点
            return deleteOneNode(cur);
        }
        // pre 要知道是删左孩子还是右孩子
        if (pre->left && pre->left->val == key) {
            pre->left = deleteOneNode(cur);
        }
        if (pre->right && pre->right->val == key) {
            pre->right = deleteOneNode(cur);
        }
        return root;
    }
};