day20

1.235.二叉搜索树的最近公共祖先：递归法：利用二叉搜索树的特性，如果遇到的结点是第一次出现在[p,q]区间中的，那么这个结点一定是最近公共祖先，pq分别出现在这个结点的左右子树中，由这个结点分化出来的任何结点尽管值在[p,q]区间，但是它们都不是公共祖先。
2.701.二叉搜索树中的插入操作：不考虑改变树结构的方法，只将其加入到树最后的空结点处。利用搜索树的特性，找到要插入结点的空结点处，并让此时的root->left/root->right等于新new出来的结点。
3.450.删除二叉搜索树中的节点：//递归，多种情况分析
        //1.没找到待删除结点，遍历到空结点,直接返回
        if(root == NULL) return root;
        //找到待删除结点
        if(root->val == key){
            //2.待删除结点为叶子结点，直接删除该节点，并返回空结点
            if(root->left == NULL && root->right == NULL){
                delete root;
                return NULL;
            }
            //3.待删除结点左孩子为空，右孩子不为空，右孩子补位，并返回
            else if(root->left == NULL){
                TreeNode* node = root->right;
                delete root;
                return node;
            }
            //4.待删除结点右孩子为空，左孩子不为空，左孩子补位，并返回
            else if(root->right == NULL){
                TreeNode* node = root->left;
                delete root;
                return node;
            }
            //5.待删除结点左右孩子都不为空，
            //则将待删除节点的左子树放到待删除节点的右子树的最左面节点的左孩子的位置
            //并返回删除节点右孩子为新的根节点。
            else{
                TreeNode* cur = root->right;
                while(cur->left){
                    cur = cur->left; 
                }//找到右子树最左边结点的孩子位置
                cur->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;