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

235. 二叉搜索树的最近公共祖先

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

利用二叉搜索树的特性进行公共节点的判断：

1. 此节点为公共节点：p、q恰好在此节点的左右棵子树上。即，root的val在p、q的val所构成的闭区间内。

2. 如果p、q的val恰好都大于root的val，则只需要考虑root->right

3. 如果p、q都小于root，则只考虑root->left

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if (root->val <= p->val && root->val >= q->val || root->val >= p->val && root->val <= q->val) return root;
        else if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        else return lowestCommonAncestor(root->left, p, q);
    }
};

更精简一点

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val > root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        else if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        else return root;
    }
};

迭代法

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        queue<TreeNode*> qu;
        qu.push(root);
        TreeNode* cur;
        while (!qu.empty()) {
            cur = qu.front();
            qu.pop();
            if (q->val < cur->val && p->val < cur->val) qu.push(cur->left);
            else if (q->val > cur->val && p->val > cur->val) qu.push(cur->right);
            else break;
        }
        return cur;
    }
};

更加精简的：

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. 二叉搜索树中的插入操作

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

?

3. 解法

先在二叉搜索树中查询val，直到找到NULL，然后将val插入该NULL。

迭代：

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

递归。相当于将在遍历至NULL的路上，重新连接原本的树，直到遇到NULL，然后把NULL换成val。

1. 参数和返回值。参数：当前节点和val。返回值：当前节点。

2. 终止条件。遇到NULL且将NULL替换为val。

3. 比较root和val确定从左子树走还是右子树走，root->left = root->left? /? root->right = root->right;

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (root == NULL) {
            TreeNode* n = new TreeNode(val);
            return n;
        }
        if (root->val > val) root->left = insertIntoBST(root->left, val);
        if (root->val < val) root->right = insertIntoBST(root->right, val);
        return root;
    }
};

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

1. LeetCode链接

力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

2. 题目描述

3. 解法

删除节点后，需要考虑是让左子树上位还是右子树上位。这道题的话，无所谓，暂且让左子树上位吧。这个时候问题来了，右子树该如何安排?

其实这道题目可以看成左子树上位后，将右子树插入左子树，因为两边都是二叉搜索树，且左子树必小于右子树，所以只要简单插入即可。

class Solution {
public:
    TreeNode* insertNode(TreeNode* root, TreeNode* key) {
        if (root == NULL) return key;
        if (key == NULL) return root;
        if (key->val > root->val) root->right = insertNode(root->right, key);
        if (key->val < root->val) root->left = insertNode(root->left, key);
        return root;
    }
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL) return NULL;
        if (root->val == key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            delete root;
            return insertNode(left, right);
        }
        if (key > root->val) root->right = deleteNode(root->right, key);
        if (key < root->val) root->left = deleteNode(root->left, key);
        return root;
    }
};

细想的话，其实如果将左子树上位，右子树一定被插在左子树中的最右节点的右节点上；如果让右子树上位，左子树一定被插在最左节点的左节点上。

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (root == NULL) return NULL;
        if (root->val == key) {
            TreeNode* left = root->left;
            TreeNode* right = root->right;
            delete root;
            if (left == NULL) return right;
            if (right == NULL) return left;
            TreeNode* cur = left;
            while (left != NULL && left->right != NULL) left = left->right;
            left->right = right;
            return cur;
        }
        if (key > root->val) root->right = deleteNode(root->right, key);
        if (key < root->val) root->left = deleteNode(root->left, key);
        return root;
    }
};

更巧妙的是，删除当前节点后，最合适的候选节点是左子树最右节点或者右子树最左节点。可以通过交换val值，将root换到底部，然后再遇到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;
    }
};