leetcode刷题

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

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(!root)
            return nullptr;
        if(root == p || root == q){
            return root;
        }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left && right) return root;
        else if(!left && right) return right;
        else if(left && !right) return left;
        else  return nullptr;
    }

二叉搜索树中的插入操作

TreeNode* insertIntoBST(TreeNode* root, int val) {
        TreeNode* node = new TreeNode(val);
        if(!root) return node;
        
        TreeNode* temp = root;
        TreeNode* pre;
        while(temp){
            if(val < temp->val){
                pre = temp;
                temp = temp->left;
            }
            else{
                pre = temp;
                temp = temp->right;
            }
        }
        if(val < pre->val){
            pre->left = node;
        }
        else{
            pre->right = node;
        }
        return root;
    }

二叉树的删除操作

我真垃圾啊，写这么多if

TreeNode* deleteNode(TreeNode* root, int key) {
        TreeNode* temp = root;
        TreeNode* pre = root;
        while(temp){
            if(temp->val < key){
                pre = temp;
                temp = temp->right;
            }
            else if(temp->val > key){
                pre = temp;
                temp = temp->left;
            }
            else{
                if(!temp->left && !temp->right){
                    if(pre->left == temp){
                        pre->left = nullptr;
                    }
                    else if(pre->right == temp){
                        pre->right = nullptr;
                    }
                    else{
                        root = nullptr;
                    }
                    break;
                }
                if(!temp->left && temp->right){
                    if(pre->left == temp){
                        pre->left = temp->right;
                    }
                    else if(pre->right == temp){
                        pre->right = temp->right;
                    }
                    else{
                        root = root->right;
                    }
                    break;
                }
                if(temp->left && !temp->right){
                    if(pre->left == temp){
                        pre->left = temp->left;
                    }
                    else if(pre->right == temp){
                        pre->right = temp->left;
                    }
                    else{
                        root = root->left;
                    }
                    break;
                }
                if(temp->left && temp->right){
                    if(pre->left == temp){
                        pre->left = temp->right;
                        TreeNode* sub = temp->right;
                        TreeNode* sub_pre = temp->right;
                        while(sub){
                            sub_pre = sub;
                            sub = sub->left;
                        }   
                        sub_pre->left = temp->left;
                        break;
                    }
                    else if(pre->right == temp){
                        pre->right = temp->right;
                        TreeNode* sub = temp->right;
                        TreeNode* sub_pre = temp->right;
                        while(sub){
                            sub_pre = sub;
                            sub = sub->left;
                        }   
                        sub_pre->left = temp->left;
                        break;
                    }
                    else{
                        TreeNode* sub = temp->right;
                        TreeNode* sub_pre = temp->right;
                        while(sub){
                            sub_pre = sub;
                            sub = sub->left;
                        }   
                        sub_pre->left = temp->left;
                        root =  temp->right;
                        break;
                    }
                    
                    
                }
            }
        }
        return root;
    }