day22_236二叉树最近公共祖先_235二叉搜索树（最近公共祖先_701插入一个节点_450删除一个节点）

1. 跨越节点的寻找p和q

if(left && right) return root; //只是对一个节点的判断，还需要其他的节点
else if(!left && right) return right;
else if(left && !right) return left;//超过了一个的节点的返回值
else return NULL;

1. 由于二叉搜索树的性质，如果当前节点在p和q的中间，说明当前节点是最近祖先，再往左子树会错过q，再往右子树会错过p。

1. 插入的节点肯定在叶子；
2. 找插入的位置，递归结束的条件root==NULL，找到插入位置，创建一个新的节点，返回节点。
3. 递归函数有没有返回值是很重要的，在这里使用的有返回值，返回树的节点。很重要的是在二叉搜索树中如果当前节点的值大于插入节点的值，插入位置就在当前节点的左子树；反之，在右子树。

//遇到空指针，找到插入位置，插入指针，返回指针
if(root == NULL){TreeNode* tmp = new TreeNode(val);return tmp;
}
//决定单层递归逻辑中的赋值操作
if(root->val > val) root->left = insertInToBst(root->left, val);
if(root->val < val) root->right = insertInToBst(root->right, val);

1. 在分析的时候有链表删除的训练想到要找到前驱，但是二叉树的节点有两个孩子，决定前驱找不到，在代码中解决这个问题是通过返回删除以后更新的节点，虽然前驱不好找，但是后继，即删除以后节点的后继是好找的，决定代码的这个逻辑。

//遇到叶子也没有找到删除节点，返回空
if(root == NULL) root NULL;
//找到删除节点，返回删除以后的值
if(root->val == key){return 删除root后的位置
}
//没找到删除节点，当前节点的数大于key，删除节点在当前节点的左子树，在左子树删除节点，更新左子树的值
if(root->val > key) root->left = delete(root->left, key);
//没找到删除节点，当前节点的数小于key，删除节点在当前节点的右子树，在右子树删除节点，更新右子树的值
if(root->val < key) root->right = delete(root->right, key);
return root;

2. 删除的情况

• 没有删除节点，返回当前节点；
• 删除节点是叶子，直接删除；
• 删除节点是分支节点，左子树为空，右子树不为空，右子树代替当前节点；
• 删除节点是分支节点，左子树不为空，右子树为空，左子树代替当前节点；
• 删除节点是分支节点，左右子树均不为空，左右子树均为二叉搜索树，找到右子树最小的节点，在该节点的左孩子插入右子树，左子树的根节点代替删除节点。

//1
if(root == NULL) return root;
if(root->val == val){//2if(root -> left == NULL && root->right == NULL ){delete root;return NULL;}//3else if(root->left == NULL && root -> rigt){TreeNode* tmp = root->right;delete root;return tmp;}//4else if(root->left && root->right == NULL){TreeNode* tmp = root->left;delete root;return tmp;}//5else{TreeNode* lefN = root->left;TreeNode* righN = root->right;while(righN->left) righN = righN->left;righN->left = lefN;righN = root->right;delete root;return righN;}
}