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

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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

struct TreeNode* traversal(struct TreeNode* cur,struct TreeNode* p,struct  TreeNode* q) {
        if (cur == NULL) return cur;

        if (cur->val > p->val && cur->val > q->val) {   
            struct TreeNode* left = traversal(cur->left, p, q);
            if (left != NULL) {
                return left;
            }
        }

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

根据二叉搜查树的特点，我们可以将情况分成三种，第一种是两个值在分别在左右子树上，第二和三情况是两个值都在左子树或者右子树上

为什么只需要处理第二三种情况

——因为不满足这两种情况的话，那一定就属于第一情况，题目中说到一个结点也是它本身的公共祖先

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

struct TreeNode* createTreeNode(int val) {
    struct TreeNode* ret = malloc(sizeof(struct TreeNode));
    ret->val = val;
    ret->left = ret->right = NULL;
    return ret;
}

struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
    if (root == NULL) {
        root = createTreeNode(val);
        return root;
    }
    struct TreeNode* pos = root;
    while (pos != NULL) {
        if (val < pos->val) {
            if (pos->left == NULL) {
                pos->left = createTreeNode(val);
                break;
            } else {
                pos = pos->left;
            }
        } else {
            if (pos->right == NULL) {
                pos->right = createTreeNode(val);
                break;
            } else {
                pos = pos->right;
            }
        }
    }
    return root;
}

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

struct TreeNode* deleteNode(struct TreeNode* root, int key){
    if (root == NULL) {
        return NULL;
    }
    if (root->val > key) {
        root->left = deleteNode(root->left, key);
        return root;
    }
    if (root->val < key) {
        root->right = deleteNode(root->right, key);
        return root;
    }
    if (root->val == key) {
        if (!root->left && !root->right) {
            return NULL;
        }
        if (!root->right) {
            return root->left;
        }
        if (!root->left) {
            return root->right;
        }
        struct TreeNode *successor = root->right;
        while (successor->left) {
            successor = successor->left;
        }
        root->right = deleteNode(root->right, successor->val);
        successor->right = root->right;
        successor->left = root->left;
        return successor;
    }
    return root;
}

有五种情况第一种为空树，第二种为树叶结点，第三四种，其中一个子结点为空，第五种左右结点都不为空

如果为空树和树叶结点的话，那么直接返回空

如果其中一个子结点为空的话，那么返回他的结点

如果左右不为空，那么找要被删除结点的右子结点的最左子结点，然后将删除的左子结点放到最左子结点的左节点。