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

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

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root==NULL)return NULL;
         if((root->val>=p->val&&root->val<=q->val)||(root->val<=p->val&&root->val>=q->val))return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right= lowestCommonAncestor(root->right,p,q);
        if(left)return left;
        if(right)return right;
        return NULL;
    }
};

701. 二叉搜索树中的插入操作
思路：将遍历路径全部进行父子节点的重新赋值，当为NULL为就赋值孩子节点为新节点，直接在树上操作。

class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(root==NULL){
            TreeNode* node=new TreeNode(val);
            return node;
        }
        if(root->val<val)root->right= insertIntoBST(root->right,val);
        if(root->val>val)root->left= insertIntoBST(root->left,val);
        return root;

    }
};

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

class Solution {
public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        if(root==NULL)return root;//没找到则返回原节点
        if(root->val==key){
            if(root->left==NULL)return root->right;//找到了左孩子为空的节点，返回右孩子
            else if(root->right==NULL)return root->left;
            else{
                //找到了左右孩子都存在的节点
                //将原节点左孩子放到原节点右孩子树的最小值（最左孩子）的左孩子节点
                TreeNode* cur=root->right;//找最左孩子节点
                while(cur->left!=NULL)cur=cur->left;
                cur->left=root->left;
                //开始删除
                TreeNode* temp=root;
                root=root->right;
                delete temp;
                return root;
            }
        }
        if(key<root->val){
            root->left= deleteNode(root->left,key);
        }
        if(key>root->val){
            root->right= deleteNode(root->right,key);
        }
        return root;
    }
};