代码随想录 10.13 || 二叉树 LeetCode 235.二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点

二叉树的定义：

        回顾一下二叉树的定义，加固记忆。

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptre) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

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

        与普通二叉树中的最近公共祖先不同，求二叉搜索树的最近公共祖先更为容易一些，因为二叉搜索树自带顺序性，我们可以根据节点的值寻找目标节点的位置。

        如果，当前节点的值同时大于 节点 p 和 q 的值，说明 p 和 q 在当前节点的左子树中，反之则位于右子树中。

        如果，当前节点的值大于其中一个节点，小于另一个节点，当前节点即为给定节点 p 和 q 的最近公共祖先。

class Solution { // 递归法
private:
    TreeNode* traversal(TreeNode *node, TreeNode *p, TreeNode *q) {
        if (node->val > p->val && node->val > q->val) return traversal(node->left, p, q);
        if (node->val < p->val && node->val < q->val) return traversal(node->right, p, q);
 
        return node;
    }
 
public:
    TreeNode* lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {
        if (root == nullptr) return root;
 
        return traversal(root, p, q);
    }
};

        在递归法中，我们递归遍历二叉树，在不满同时大于或小于条件时，直接返回当前节点，即最近公共祖先。

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

        迭代法代码则更为简洁，使用 while 一直向下遍历，直至找到目标节点为止，如果未找到，则说明目标不存在给定二叉树中。

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

        向一颗二叉搜索树中插入一个节点，众所周知，在二叉搜索树中，左子树的值一定小于根节点的值，右子树的值一定大于根节点的值，我们需要找到合适的位置插入给定节点，而不是应该随意插入，插入完成后的树，应该保持二叉搜索树的性质。

class Solution { // 递归法
private:
    TreeNode* traversal(TreeNode *node, int val) {
        if (node->val > val && node->left != nullptr) return traversal(node->left, val);
        if (node->val < val && node->right != nullptr) return traversal(node->right, val);
 
        return node;
    }
 
public:
    TreeNode* insertIntoBST(TreeNode *root, int val) {
        if (root == nullptr) {
            TreeNode *node = new TreeNode(val);
            return node;
        }
 
        TreeNode *fnode = traversal(root, val);
        TreeNode *cnode = new TreeNode(val);
 
        if (fnode->val > val) fnode->left = cnode;
        else fnode->right = cnode;
 
        return root;
    }
};

        在递归法中，我们仍然利用二叉搜索树的性质，寻找插入位置。如果，待插入节点的值小于当前节点，且当前节点的左子树不为空，则向左子树遍历；如果，待插入节点的值大于当前节点，且当前节点的右子树不为空，则向右子树遍历。不满足上述条件，则说明当前节点的左子树或右子树为空，此时我们就找到了插入位置的父节点，将其返回。在主函数中，我们定义一个 fnode 接收返回节点，然后以 val 初始化一个节点，并根据 val 的值，将其添加到 fnode 的左子树或右子树上。在最后，返回更新过后的 root 即可。

class Solution { // 迭代法
public:
    TreeNode* insertIntoBST(TreeNode *root, int val) {
        if (root == nullptr) {
            TreeNode *node = new TreeNode(val);
            return node;
        }
 
        TreeNode *cur = root;
        while(1) {
            if (cur->val > val && cur->left != nullptr) cur = cur->left;
            else if (cur->val < val && cur->right != nullptr) cur = cur->right;
            else break;
        }
 
        TreeNode *node = new TreeNode(val);
        if (cur->val > val) cur->left = node;
        else cur->right = node;
 
        return root;
    }
};

        迭代法代码更为简洁，同样利用循环找位置，然后添加新节点至目标位置。

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

        与向二叉搜索树中添加节点不同，从树中删除节点会破坏树的结构，涉及到树的重塑。分析，如果删除二叉搜索树中的某一个节点，存在以下四种情况：

        1）待删除节点为叶子节点，不需要更改树的结构，直接将待删除节点置空；

        2）待删除节点的左叶子节点不为空，右叶子节点为空，将待删除节点的左子树上移；

        3）待删除节点的左叶子节点为空，右叶子节点不为空，将待删除节点的右子树上移；

        4）如果待删除节点的左右子树都不为空，需要更改二叉搜索树的结构，以确保删除节点后，仍然保持二叉搜索树的性质。可以将待删除节点的左子树挂到右子树的最左节点下，也可将待删除节点的右子树挂到左子树的最右节点下，在此我们选择第一种方法。

class Solution {
public:
    TreeNode* deleteNode(TreeNode *root, int key) {
        if (root == nullptr) return root;
        
        if (root->val == key) {
            if (root->left == nullptr && root->right == nullptr){
                delete root;
                return nullptr;
            } else if (root->left == nullptr && root->right != nullptr) {
                TreeNode *node = root->right;
                delete root;
                return node;
            } else if (root->left != nullptr && root->right == nullptr) {
                TreeNode *node = root->left;
                delete root;
                return node;
            } else {
                TreeNode *node = root->right;
                while (node->left != nullptr) node = node->left;
                node->left = root->left;
 
                TreeNode *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;
    }
};

        在最后返回根节点 root，如果删除发生在左子树，则用左子树接收变更后的左子树，右子树亦然。