代码随想录算法训练营Day-20 | 235. 二叉搜索树的最近公共祖先、701.二叉搜索树中的插入操作、450.删除二叉搜索树中的节点
经过Day18的递归悟道之后，看递归的题都十分清晰了。
235. 二叉搜索树的最近公共祖先
1.递归函数作用：传入二叉搜索树根节点和p、q节点，返回遇到的第一个值在p、q值中间的节点，对于二叉搜索树，该节点就是p、q共同祖先
2.终止条件：遇到空节点返回空（其实不写都行，题目不会出现空节点且不会出现不合法情况，所以一定在遍历到空节点之前就找到了）
3.递归逻辑：如果当前根节点值大于pq两值，往左遍历，小于就往右遍历。
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){ return lowestCommonAncestor(root->left,p,q); } if(root->val < p->val && root->val < q->val){ return lowestCommonAncestor(root->right,p,q); } return root; } };701.二叉搜索树中的插入操作
1.递归函数作用：对于非空节点，把值节点插入后，返回根节点；对于空节点，创建值节点并返回
2.终止条件：遇到空节点就创建值节点并返回值节点（返回后会有上一层节点的左右子树接收）
3.递归逻辑：如果当前根节点值大于值说明插入位置在左边，所以把左子树的返回结果放到左子树位置，即更新左子树为插入新节点后的左子树；当前根节点值小于值的情况同理。
class Solution { public: //函数作用是：对于非空节点，把值节点插入后，返回根节点 //对于空节点：创建值节点并返回 TreeNode* insertIntoBST(TreeNode* root, int val) { if(root == NULL){ TreeNode* node = new TreeNode(val); return node; } //如果当前根节点值大于值说明插入位置在左边，所以把左子树的返回结果放到左子树位置，即更新左子树为插入新节点后的左子树 if(root->val>val) root->left = insertIntoBST(root->left,val); //同理 if(root->val<val) root->right = insertIntoBST(root->right,val); return root; } };450.删除二叉搜索树中的节点
分析：
删除有以下几种情况：
1.当前根节点不是要删的节点；
2.当前根节点是要删的节点，且左为空右为空；
3.当前根节点是要删的节点，且左不为空右为空；
4.当前根节点是要删的节点，且左为空右不为空；
5.当前根节点是要删的节点，且左右都不为空。
递归写法：
1.递归函数作用：树中有key节点，删除key节点，并返回新的根节点；树中没有key节点，不执行删除操作，依旧返回原根节点
2.终止条件：针对五种情况，各自都算终止条件，每个情况执行对应的处理
3.递归逻辑：如果当前值大于key，说明节点在左子树上，所以对左子树执行递归调用，更新到左子树位置；如果当前值小于key的话同理。
class Solution { public: TreeNode* deleteNode(TreeNode* root, int key) { //终止条件：包含五种情况处理逻辑 if(root == NULL) return NULL; if(root->val == key){ if(root->left==NULL && root->right==NULL){ delete root; return NULL; } else if(root->left!=NULL && root->right==NULL){ auto reNode = root->left; delete root; return reNode; } else if(root->left==NULL && root->right!=NULL){ auto reNode = root->right; delete root; return reNode; } else{//先找到右子树最左边的元素，把左子树放到该元素的左边，再返回右子树节点 TreeNode* cur = root->right; while(cur->left!=NULL) cur = cur->left; cur->left = root->left; auto reNode = root->right; delete root; return reNode; } } if(root->val > key) root->left = deleteNode(root->left,key); if(root->val < key) root->right = deleteNode(root->right,key); return root; } };