title: 二叉搜索树的插入删除修剪

? 题目一描述

题目链接：701. 二叉搜索树中的插入操作

? 解题思路

递归法：

明确BST插入可以不用改变树的结构，所以找到对应的子节点插入即可；

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == nullptr) {
            return new TreeNode(val);
        }

        if (val > root->val) root->right = insertIntoBST(root->right, val);
        if (val < root->val) root->left = insertIntoBST(root->left, val);
        return root;
    }
};

迭代法：

找到叶子节点，但是是迭代的，无法像递归一样利用函数调用的栈，但是可以采用pre 来记录上一个的节点！

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* cur = root;
        TreeNode* pre = nullptr;
        while (cur) {
            pre = cur;
            if (cur->val > val) {
                cur = cur->left;
            }
            else if (cur->val < val) {
                cur = cur->right;
            }
        }
        if (pre && pre->val > val) pre->left = new TreeNode(val);
        else if (pre && pre->val < val) pre->right = new TreeNode(val);
        else root = new TreeNode(val);
        return root;
    }
};

? 复杂度分析

• 时间复杂度：O(n);
• 空间复杂度：O(1);

? 题目二描述

题目链接：450. 删除二叉搜索树中的节点

? 解题思路

找到删除节点要观察：

情况一：要删除的节点是叶子节点，直接删除即可；

情况二：要删除的节点是只存有一边子树，直接删除用子树的第一个节点替上来就可；

情况三：要删除的节点存在左右两边子树，那么删除可以有多种选择方案，这里提两种

• 方案①：用删除节点的右子树第一个节点替代，如图：
• 方案②用删除节点的右子树最小值来替代，如上图，用4代替7；

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return nullptr; // 处理找不到的情况；
        if (root->val == key) {
            // 处理情况一、二
            if (root->left == nullptr) {
                TreeNode* cur = root->right;
                delete root;
                return cur;
            }
            if (root->right == nullptr) {
                TreeNode* cur = root->left;
                delete root;
                return cur;
            }
            // 情况三
            if (root->left && root->right) {
                TreeNode* node = root->right;
                while (node->left) node = node->left; // 拿到右子树最小的值；
                // 方案①:将右子节点替上去；
                node->left = root->left;
                TreeNode* cur = root->right;
                delete root;
                return cur;
                //方案②：将右子树中的最小值替上去；
                node = new TreeNode(node->val);
                root->right = deleteNode(root->right, node->val);
                node->left = root->left; node->right = root->right;
                delete root;
                return node;
            }
        }
        // 找左右子树
        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* deleteoOne(TreeNode* root) {
        // 情况一、二
        if (root->right == nullptr) return root->left;
        if (root->left == nullptr) return root->right;
        // 情况三，采用方案①
        TreeNode* cur = root->right;
        while (cur->left) cur = cur->left;
        cur->left = root->left;
        return root->right; 
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == nullptr) return nullptr;
        TreeNode* pre = nullptr;
        TreeNode* cur = root;
        while (cur) {
            if (cur->val == key) break;
            pre = cur;
            if (cur->val > key) cur = cur->left;
            else cur =cur->right;
        }
        // 如果要删除的是头节点
        if (pre == nullptr) return deleteoOne(cur);
        // 如果要删除的是pre左孩子节点
        if (pre->left && pre->left == cur) pre->left = deleteoOne(cur);
        // 如果要删除的是pre右孩子节点
        if (pre->right && pre->right == cur) pre->right = deleteoOne(cur);
        return root;
    }
};

? 复杂度分析

• 时间复杂度：O(n);
• 空间复杂度：O(1);

? 题目三描述

题目链接：669. 修剪二叉搜索树

? 解题思路

解法一：递归

利用BST树的性质，要明确当下节点可能 不再[low, high]区间内，但是其左子树或者右子树是存在这样的节点的；

自底而上不断改变树的结构，剔除不再[low,high]的节点，有：

• 当前节点val < low ，那么它的右子树一定是在[low， high]区间内；
• 相同的，val >high, 那么它的左子树一定在[low， high]区间内

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        if (root == nullptr) return nullptr;
        // 自底向上改变
        root->left = trimBST(root->left, low, high);
        root->right = trimBST(root->right, low, high);
        if (root->val > high) return root->left;
        else if (root->val < low) return root->right;
        else return root;
    }
};

解法二：迭代

看代码注释即可，思考应该返回什么？怎么修剪左右子树？

class Solution {
public:
    TreeNode* trimBST(TreeNode* root, int low, int high) {
        // 找到第一个符合[low, high] 的节点（当返回值）；
        while (root && (root->val < low || root->val > high)) {
            if (root->val < low) root = root->right; // 当前值 < low
            else root = root->left; // 当前值 > low
        }
        // 修剪左子树
        TreeNode* cur =root;
        while (cur != nullptr) {
            while (cur->left && cur->left->val < low) { //找到符合[low, high]的节点 接入left
                cur->left = cur->left->right; 
            }
            cur = cur->left;
        }
        // 修剪右子树
        cur = root;
        while (cur != nullptr) {
            while (cur->right && cur->right->val > high) { //找到符合[low, high]的节点 接入right
                cur->right = cur->right->left;
            }
            cur = cur->right;
        }

        return root;
    }
};

? 复杂度分析

• 时间复杂度：O(n);
• 空间复杂度：O(1);