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

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

代码随想录链接

题目

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

给定一个二叉搜索树和两个指定节点, 在这个二叉树中找到这两个指定节点的最近公共祖先.

自己的想法

和昨天的236题一样, 使用递归法来找这两个节点的最近公共祖先, 实测昨天的代码也是可以直接AC的. 但这没有利用到二叉树的特性.

二叉树的特性的存在, 使得找节点更有方向性. 当前遍历节点的值小于两个目标节点, 则向遍历节点的右侧查找; 否则就向左侧查找.

题解

递归法:

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return NULL;
        if (root -> val > p -> val && root -> val > q -> val) return lowestCommonAncestor(root -> left, p, q);  // 节点值大于两个目标节点, 向左侧查找
        if (root -> val < p -> val && root -> val < q -> val) return lowestCommonAncestor(root -> right, p, q); // 节点值小于两个目标节点, 向右侧查找
        return root;  // 若落在两个节点的区间内, 则为要找的节点
    }
};

迭代法:

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 root;
    }
};

701.二叉搜索树中的插入操作

代码随想录链接

题目

701.二叉搜索树中的插入操作

向二叉搜索树种插入含有给定值的节点.

自己的想法

题目没有要求是平衡二叉树, 所以直接按照大小顺序遍历到一个空位置进行插入即可.

题解

递归法:

class Solution {
private:
    void traversal(TreeNode* cur, TreeNode* pre, int val) { // pre 标记上一个节点
        if (cur == NULL) {                                  // 当前节点不存在, 则给上一个节点插入一个包含给定值的孩子节点
            TreeNode *node = new TreeNode(val);
            if (val > pre -> val) pre -> right = node;
            else pre -> left = node;
            return;
        }
        if (cur -> val > val) traversal(cur -> left, cur, val); // 给定值大于当前节点值, 向左找空位
        if (cur -> val < val) traversal(cur -> right, cur, val); // 给定值小于当前节点值, 向右找空位
        return;        
    }
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) root = new TreeNode(val);
        else traversal(root, NULL, val);
        return root;
    }
};

迭代法: (和二叉搜索树的遍历类似)

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if (!root) {
            TreeNode *node = new TreeNode(val);
            return node;
        }
        TreeNode *pre = NULL, *cur = root;
        while (cur) {   // 找合适的空位
            pre = cur;  // 标记上一个节点
            if (cur -> val > val) cur = cur -> left;
            else cur = cur -> right;
        }
        if (pre) {  // 生成节点并插入到pre的左孩子或者右孩子位置
            if (pre -> val > val) pre -> left = new TreeNode(val);
            else pre -> right = new TreeNode(val);
        }
        return root;
    }
};

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

代码随想录链接

题目

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

删除二叉搜索树中给定值的节点.

自己的想法

通过二叉搜索树的查找, 先找到要删除的节点, 然后再结合左右孩子的情况调整要删除的节点之于其父节点的指针.

题解

递归法:

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if (!root) return nullptr;
        if (root -> val == key) {           // 若当前节点是要被删除的节点
            if (!(root -> left) && !(root -> right)) {  // 如果没有子节点, 就直接删除
                delete root;
                return nullptr;
            } else if (!(root -> left) || !(root -> right)) { // 如果有一个子节点, 就将子节点代替原来节点
                auto node = !(root -> left) ? root -> right : root -> left;
                delete root;
                return node;
            } else { // 如果有两个子节点, 就在右子树中找最左侧的节点(没有左子树的节点), 将被删除的节点的左子树移动到这个节点的左孩子位置上, 并用原节点的右孩子代替被删除节点的位置.
                auto cur = root -> right;
                while (cur -> left) {
                    cur = cur -> left;
                }
                cur -> left = root -> left;
                auto tmp = root;
                root = root -> right;
                delete tmp;
                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) return nullptr;
        if (root -> val == key) {               // 找到了目标节点
            if (!(root -> right)) return root -> left; // 如果没有右孩子, 就拿左孩子来代替被删除的节点
            auto cur = root -> right;           // 取右子树中最左侧的节点, 交换与被删除的节点的值
            while (cur -> left) cur = cur -> left;
            swap(root -> val, cur -> val);
        }                       // 被交换至没有左子树的节点之后, 再次被遍历时, 会再次被挪到右子树的最左侧节点, 当被挪到叶子节点时再被遍历到, 会被以NULL形式覆盖掉, 完成真正的删除
        root -> left = deleteNode(root -> left, key);   // 递归删除包含给定值的节点
        root -> right = deleteNode(root -> right, key);
        return root;
    }
};

迭代法, 删除的逻辑和上面是一样的, 只是找要被删除的节点的过程是迭代的:

class Solution {
private:
    TreeNode* deleteTheNode(TreeNode* target) {
        if (!target) return nullptr;
        if (!(target -> right)) return target -> left;
        auto 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) return nullptr;
        auto cur = root;
        TreeNode *pre = nullptr;
        while (cur) {
            if (cur -> val == key) break;
            pre = cur;
            if (cur -> val > key) cur = cur = cur -> left;
            else cur = cur -> right;
        }
        if (!pre && root -> val == key) return deleteTheNode(root);
        if (pre -> left && pre -> left -> val == key) pre -> left = deleteTheNode(cur);
        if (pre -> right && pre -> right -> val == key) pre -> right = deleteTheNode(cur); 
        return root;
    }
};