算法随想Day20【二叉树】| LC235-二叉搜索树的最近公共祖先、LC701-二叉搜索树中的插入操作、LC450-删除二叉搜索树中的节点

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

利用二叉搜索树的特性，中序遍历，如果当前节点的值大于q和p的值，公共祖先一定在当前节点的左子树中，同理小于q和p值时，公共祖先一定在当前节点的右子树。一旦找到介于p和q之间值的节点，则一定是最近公共祖先

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
    TreeNode* result = nullptr;
    if (root == nullptr)
    {
        return nullptr;
    }
    if (root->val >= p->val && root->val <= q->val || root->val <= p->val && root->val >= q->val)
    {
        result = root; 
    }
    if (root->val < p->val && root->val < q->val)
    {
        result = lowestCommonAncestor(root->right, p, q);
    }
    if (root->val > p->val && root->val > q->val)
    {
        result = lowestCommonAncestor(root->left, p, q);
    }
    return result;
}

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

不难，直接贴代码

TreeNode* insertIntoBST(TreeNode* root, int val)
{
    TreeNode* newNode = new TreeNode(val);
    TreeNode* curr = nullptr;
    TreeNode* prev = nullptr;
    if (root == nullptr)
    {
        root = newNode;
        return root;
    }
    curr = root;
    while (curr != nullptr)
    {
        prev = curr;
        if (curr->val > val)
            curr = curr->left;
        else if (curr->val < val)
            curr = curr->right; 
    }
    if (prev->val > val)
        prev->left = newNode;
    else if (prev->val < val)
        prev->right = newNode;

    return root;
}

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

听了Carl哥的分析，自己做一遍：

利用二叉搜索树的特性，进行中序遍历直到找到要删除的节点。若找到相应节点，分5种情况处理：

• 没找到删除的节点，遍历到空节点直接返回了
• 左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
• 删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点
• 删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
• 左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。

TreeNode* deleteNode(TreeNode* root, int key)
{
    TreeNode* temp = nullptr;
    if (root == nullptr)
    {
        return nullptr;
    }
    if (root->val == key)
    {
        if (root->left == nullptr && root->right == nullptr)
        {
            return nullptr;
        }
        if (root->left == nullptr && root->right != nullptr)
        {
            temp = root->right;
            delete root;
            return temp;
        }
        if (root->left != nullptr && root->right == nullptr)
        {
            temp = root->left;
            delete root;
            return temp;
        }
        if (root->left != nullptr && root->right != nullptr)
        {
            temp = root->right;
            ////让temp指向当前要删除节点的右子树中的最左节点
            while (temp->left != nullptr)
            {
                temp = temp->left;
            }
            temp->left = root->left;
            temp = root->right;
            delete root;
            return temp;
        }
    }

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