235. 二叉搜索树的最近公共祖先
卡哥建议：相对于 二叉树的最近公共祖先 本题就简单一些了，因为 可以利用二叉搜索树的特性。
题目链接/文章讲解：https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html
做题思路：
理解了二叉树的最近公共祖先那道题后，那这道题无非利用了二叉搜索树的特点，因为是有序树，所有 如果 中间节点是 q 和 p 的公共祖先，那么 中节点的数组 一定是在 [p, q]区间的。即 中节点 > p && 中节点 < q 或者 中节点 > q && 中节点 < p。把二叉搜索树以中序遍历的方式写成数组也好理解这点。
所以当我们从上向下去递归遍历，第一次遇到 cur节点是数值在[p, q]区间中，那么cur就是 p和q的最近公共祖先。如下图，第一次遇到后，就不用向左或向右遍历了。
在遍历二叉搜索树的时候就是寻找区间[p->val, q->val]（注意这里是左闭右闭）。
如果 cur->val 大于 p->val，同时 cur->val 大于q->val，那么就应该向左遍历（说明目标区间在左子树上），因为左子树比根节点小，右子树比根节点大，如果cur值此时都大于区间 [p,q]，说明不在右子树那边，所以要向左遍历。需要注意的是此时不知道p和q谁大，所以两个都要判断；
如果 cur->val 小于 p->val，同时 cur->val 小于 q->val，那么就应该向右遍历（目标区间在右子树），原因同理。
剩下的情况，就是cur节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。
本题代码：
1 class Solution {
2 private:
3 TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
4 if (cur == NULL) return cur;
5 // 中
6 if (cur->val > p->val && cur->val > q->val) { // 左
7 TreeNode* left = traversal(cur->left, p, q);
8 if (left != NULL) {
9 return left;
10 }
11 }
12
13 if (cur->val < p->val && cur->val < q->val) { // 右
14 TreeNode* right = traversal(cur->right, p, q);
15 if (right != NULL) {
16 return right;
17 }
18 }
19 return cur;//else 的情况
20 }
21 public:
22 TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
23 return traversal(root, p, q);
24 }
25 };
701.二叉搜索树中的插入操作
卡哥建议：本题比想象中的简单，大家可以先自己想一想应该怎么做，然后看视频讲解，就发现 本题为什么比较简单了。
题目链接/文章讲解：https://programmercarl.com/0701.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C.html
视频讲解：https://www.bilibili.com/video/BV1Et4y1c78Y
做题思路：
这里看卡哥视频理解的思路更清晰。
只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。
本题代码：
1 class Solution {
2 public:
3 TreeNode* insertIntoBST(TreeNode* root, int val) {
4 if (root == NULL) {
5 TreeNode* node = new TreeNode(val);
6 return node;
7 }
8 if (root->val > val) root->left = insertIntoBST(root->left, val);//插入新节点的值小于根节点的值，就向左遍历
9 if (root->val < val) root->right = insertIntoBST(root->right, val);
10 return root;
11 }
12 };
450.删除二叉搜索树中的节点
卡哥建议：相对于 插入操作，本题就有难度了，涉及到改树的结构
题目链接/文章讲解：https://programmercarl.com/0450.%E5%88%A0%E9%99%A4%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
视频讲解：https://www.bilibili.com/video/BV1tP41177us
做题思路：
二叉搜索树中删除节点遇到的情况都搞清楚。
有以下五种情况：
- 第一种情况：没找到删除的节点，遍历到空节点直接返回了
- 找到删除的节点
- 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
- 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点，这里画个图就能理解。
- 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
- 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
本题代码：
1 class Solution {
2 public:
3 TreeNode* deleteNode(TreeNode* root, int key) {
4 if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
5 if (root->val == key) {
6 // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
7 if (root->left == nullptr && root->right == nullptr) {
8 ///! 内存释放
9 delete root;
10 return nullptr;
11 }
12 // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
13 else if (root->left == nullptr) {
14 auto retNode = root->right;
15 ///! 内存释放
16 delete root;
17 return retNode;
18 }
19 // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
20 else if (root->right == nullptr) {
21 auto retNode = root->left;
22 ///! 内存释放
23 delete root;
24 return retNode;
25 }
26 // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
27 // 并返回删除节点右孩子为新的根节点。
28 else {
29 TreeNode* cur = root->right; // 找右子树最左面的节点
30 while(cur->left != nullptr) {
31 cur = cur->left;
32 }
33 cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
34 TreeNode* tmp = root; // 把root节点保存一下，下面来删除
35 root = root->right; // 返回旧root的右孩子作为新root
36 delete tmp; // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
37 return root;
38 }
39 }
40 if (root->val > key) root->left = deleteNode(root->left, key);//这里相当于把新的节点返回给上一层，上一层就要用 root->left 或者 root->right接住，
41 if (root->val < key) root->right = deleteNode(root->right, key);
42 return root;
43 }
44 };