二叉搜索树的最近公共祖先
题目链接：235. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）
题目描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 输出: 6 解释: 节点2和节点8的最近公共祖先是6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 输出: 2 解释: 节点2和节点4的最近公共祖先是2, 因为根据定义最近公共祖先节点可以为节点本身。
题解：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/class Solution {
private:TreeNode* traversal(TreeNode*cur, TreeNode* p, TreeNode* q){//遇到空直接返回，结束条件if(cur == NULL) return cur;//使用前序遍历，但我们不需要处理中节点逻辑，所以跳过中逻辑，直接实现左右节点逻辑if(cur->val > q->val && cur->val > p->val){TreeNode* left = traversal(cur->left, p, q);//搜索一条边的逻辑if(left != NULL){return left;}}if(cur->val < q->val && cur->val < p->val){TreeNode* right = traversal(cur->right, p, q);if(right != NULL){return right;}}//其他情况就是cur->val在q,p的区间内，此时cur就是q,p的最近公共祖先,因此直接返回return cur;}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root, p, q);}
};总结与思考：
- 解决此题我们需要利用二叉搜索树的性质，需要明白一个既定事实：当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[q, p]区间中，那么cur就是 q和p的最近公共祖先。而关于递归遍历顺序，因为此题不涉及到“中”逻辑的处理，因此使用什么递归遍历顺序都无所谓，所以我们默认使用前序遍历的顺序来做题解
- 递归的三要素：
- 递归函数的参数和返回值：需要记录当前节点和目标q,p，所以参数为cur,q,p返回值是要返回最近公共祖先，所以类型为TreeNode*
- 递归函数的结束条件：遇到空就直接返回，此题提示说明一定有结果，所以这里的递归结束条件可以省略
- 递归函数的单层递归逻辑：因为不清楚q,p谁大谁小，因此在利用二叉搜索树性质向左或向右递归时，cur->val的值需要与q->val,p->都要比较。这里只需要写单独搜索一条边的实现逻辑，不需要递归整个树的所有分支。两个if递归处理了所有不符合的情况，因此剩下的情况均为找到了最近公共祖先的情况，直接返回cur即可
二叉搜索树中的插入操作
题目链接：701. 二叉搜索树中的插入操作 - 力扣（LeetCode）
题目描述：
给定二叉搜索树（BST）的根节点 root 和要插入树中的值 value ，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
示例 1：
输入：root = [4,2,7,1,3], val = 5 输出：[4,2,7,1,3,5] 解释：另一个满足题目要求可以通过的树是：
示例 2：
输入：root = [40,20,60,10,30,50,70], val = 25 输出：[40,20,60,10,30,50,70,null,null,25]
示例 3：
输入：root = [4,2,7,1,3,null,null,null,null,null,null], val = 5 输出：[4,2,7,1,3,5]
题解：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* insertIntoBST(TreeNode* root, int val) {//寻找插入节点的位置，再把添加的节点返回上一层，完成父子节点的赋值if(root == nullptr){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. 删除二叉搜索树中的节点 - 力扣（LeetCode）
题目描述：
给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。
一般来说，删除节点可分为两个步骤：
- 首先找到需要删除的节点；
- 如果找到了，删除它。
示例 1:
输入：root = [5,3,6,2,4,null,7], key = 3 输出：[5,4,6,2,null,null,7] 解释：给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。 另一个正确答案是 [5,2,6,null,4,null,7]。
示例 2:
输入: root = [5,3,6,2,4,null,7], key = 0 输出: [5,3,6,2,4,null,7] 解释: 二叉树不包含值为 0 的节点
示例 3:
输入: root = [], key = 0 输出: []
题解：
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {//第一种情况：没找到删除节点，遍历到空节点返回if(root == nullptr) return root;if(root->val == key){//第二种情况：左右孩子节点都为空，直接删除节点，返回NULL为根节点if(root->left == nullptr && root->right == nullptr){delete root;return nullptr;}//第三种情况：左孩子为空，右孩子不为空，则删除节点后，右孩子补位，返回右孩子为根节点else if(root->left == nullptr && root->right != nullptr){auto retNode = root->right;delete root;return retNode;}//第四种情况：左孩子不为空，右孩子为空，则删除节点后，左孩子补位，返回左孩子为根节点else if(root->left != nullptr && root->right == nullptr){auto retNode = root->left;delete root;return retNode;}//第五种情况：左右孩子都不为空，则删除节点后，将左子树嫁接到右子树最左边节点的左孩子位置处//并且返回删除节点的右孩子作为根节点else{//先寻找右子树最左边节点的左孩子位置TreeNode* cur = root->right;while(cur->left != nullptr){cur = cur->left;}//将左孩子嫁接到右子树最左边节点的左孩子位置cur->left = root->left;//保存一下root节点TreeNode* temp = root;//将右孩子更新为新的根节点root = root->right;delete temp;return root;}}//根据二叉搜索树的性质递归if(root->val > key) root->left = deleteNode(root->left, key);if(root->val < key) root->right = deleteNode(root->right, key);return root;}
};总结与思考：
- 我们使用递归法来解决删除二叉搜索树的节点这道题，因为涉及到改变树的结构，因此需要考虑在删除目标节点后，返回的根节点的情况有哪些，因此需要考虑目标节点的左右孩子状态和一些特殊情况思考
- 递归三要素：
- 递归函数的参数和返回值：给出二叉搜索树的根节点和需要删除的目标节点值key，我们可以通过递归返回值删除节点。
- 递归函数的结束条件：遇到空返回，其实这也说明没找到删除的节点，遍历到空节点直接返回了
- 递归函数的单层递归逻辑：我们需要清晰所有二叉搜索树中删除节点遇到的情况，分五种情况，具体实现在代码中有详细注释。
- 这里总结的五种情况为：
- 没有找到删除的节点，遍历到空节点后直接返回了
- 找到了删除的节点时，删除节点的左右孩子都为空，则删除目标节点后以NULL为根节点返回
- 找到了删除的节点时，删除节点的左孩子为空，右孩子不为空，则删除目标节点后，右孩子补位作为新的根节点返回
- 找到了删除的节点时，删除节点的左孩子不为空，右孩子为空，则删除目标节点后，左孩子补位作为新的根节点返回
- 找到了删除的节点时，删除节点的左右孩子均不为空，则删除目标节点后，需要将删除节点的左孩子放置到右孩子最左边节点位置的左孩子处，并且将删除节点的右孩子作为新的根节点返回
的多进程 + 单线程协程、Gin (Go)Go的单进程 + 多 goroutine 解说)
