链接
235. 二叉搜索树的最近公共祖先
701.二叉搜索树中的插入操作
450.删除二叉搜索树中的节点
初次尝试
235. 二叉搜索树的最近公共祖先
拿到本题，我发现这道题和236. 二叉树的最近公共祖先基本相同，只不过二叉树的条件被增强为二叉搜索树。我首先尝试用236题的思路和代码解决本题。据此，我独立写出了以下的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 终止条件1
if (root == NULL) return NULL;
// 终止条件2
if (root == p || root == q) return root;
// 后序遍历
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left && right) return root;
if (left) return left;
if (right) return right;
return NULL;
}
};
然后尝试利用二叉搜索树的特性来进行优化。我想到的优化是：用双指针后序遍历二叉搜索树，若pre和cur分别指向两个目标节点，那么cur就是两节点的最近公共祖先。直接看卡尔的讲解吧。
701.二叉搜索树中的插入操作
本题应该充分利用二叉搜索树的性质就可以求解。若插入节点的值大于当前节点，则向当前节点的右子树插。若插入节点的值小于当前节点，则向当前节点的左子树插。我选择的策略是尽量往叶子节点那一层插入。根据这个思路，我写下了如下的代码（迭代写法，实际上就是枚举将val节点插入二叉搜索树的各种可能）：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
// root为空，则直接返回由val创建的节点
if (root == NULL) return new TreeNode(val);
// 后序移动cur指针，不要直接移动root
TreeNode* cur = root;
while (cur)
{
// cur无左子节点的情况，则条件合适就将val节点作为cur的左子节点
if (cur->left == NULL && val < cur->val)
{
TreeNode* insert = new TreeNode(val);
cur->left = insert;
return root;
}
// cur无右子节点的情况，则条件合适就将val节点作为cur的右子节点
if (cur->right == NULL && val > cur->val)
{
TreeNode* insert = new TreeNode(val);
cur->right = insert;
return root;
}
// 否则继续走到叶子节点位置，在叶子节点之下插入val节点
if (val > cur->val) cur = cur->right;
else if (val < cur->val) cur = cur->left;
if (cur->left == NULL && cur->right == NULL)
{
TreeNode* insert = new TreeNode(val);
if (val > cur->val) cur->right = insert;
else cur->left = insert;
return root;
}
}
// 必须随便返回一个东西，虽然必然不会执行这行代码，但不返回一个东西本程序就会报错
return NULL;
}
};
注意，上述写法一定要区分cur指针和root节点。在写出了迭代写法后，应该也可以根据相同的原理写出递归写法。递归的写法其实非常简单，我尝试了一段时间后写出了如下的代码：1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 终止条件
if (root == NULL) return new TreeNode(val);
// 要插入的节点的值小于root节点的值，则将其插入root节点的左子树
if (root->val > val) root->left = insertIntoBST(root->left, val);
// 要插入的节点的值大于root节点的值，则将其插入root节点的右子树
else if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
450.删除二叉搜索树中的节点
本题的难点在于删除二叉搜索树中的节点后，要调整二叉树的结构，甚至要改变root节点。我想到的办法就是中序遍历时使用双指针。当cur指针找到要删去的节点时，cur指针再向后移动一位，然后直接用cur指针指向pre指针，就完成了对要删去节点的删除。根据这个算法思路，我尝试写代码，但写不出来，直接看卡尔的讲解。
实现
235. 二叉搜索树的最近公共祖先
基于236. 二叉树的最近公共祖先，要好好利用二叉搜索树的特性。思路：从上往下遍历二叉树，若当前遍历的节点的值大于p和q的值，则p和q的最近公共祖先一定在当前节点的左子树中，此时从当前遍历的节点开始向左遍历。若当前遍历的节点的值小于p和q的值，则p和q的最近公共祖先一定在当前节点的右子树中，此时从当前遍历的节点开始向右遍历。若当前遍历的节点的值在p和q之间，则当前节点就是p和q的公共节点。
现在的问题是，当前节点是否是p和q的最近公共祖先？其实是的。因为p和q分别在当前节点的左右子树中，如果从当前节点开始继续向下遍历，那么不是错过p就是错过q。接下来开始写递归法的代码。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
{
// 终止条件
if (cur == NULL) return NULL;
// 单层递归逻辑
// 本题不用涉及前中后序，因为二叉搜索树本身是有序的，只要有左和右即可，中在哪里都可以
// 若当前遍历的节点的值大于p和q的值，则p和q的最近公共祖先一定在当前节点的左子树中，此时从当前遍历的节点开始向左遍历
if (cur->val > p->val && cur->val > q->val)
{
TreeNode* left = traversal(cur->left, p, q);
// 在向左遍历的过程中找到了p和q的最近公共祖先，则返回之
if (left != NULL) return left;
}
// 若当前遍历的节点的值小于p和q的值，则p和q的最近公共祖先一定在当前节点的右子树中，此时从当前遍历的节点开始向右遍历
if (cur->val < p->val && cur->val < q->val)
{
TreeNode* right = traversal(cur->right, p, q);
// 在向右遍历的过程中找到了p和q的最近公共祖先，则返回之
if (right != NULL) return right;
}
// 剩下的情况：当前节点的值在p和q之间，则当前节点就是p和q的最近公共祖先
return cur;
}
本题迭代法的代码也比较简单，原因是二叉搜索树确定了搜索的方向。迭代法代码如下所示：1
2
3
4
5
6
7
8
9
10TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
{
while (cur)
{
if (cur->val > p->val && cur->val > q->val) cur = cur->left;
else if (cur->val < p->val && cur->val < q->val) cur = cur->right;
else return cur;
}
return NULL; // 一定不要忘记这句话，否则函数会因为没有返回值报错
}
对于二叉搜索树的题目，迭代法似乎比递归法还更简单。
701.二叉搜索树中的插入操作
插入新节点的方式有多种，得到的二叉搜索树不唯一。必然可以在二叉搜索树的叶子节点处插入新的节点。若在二叉搜索树的其他位置处插入节点，则改变了二叉搜索树的结构，将本题做复杂了。递归法代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19TreeNode* insert(TreeNode* root, int val)
{
// 终止条件
// 卡尔的理解：遍历到空节点（叶子节点的左子节点或右子节点）时，将val节点作为叶子节点的左子节点或者右子节点
// 此时将val节点向上返回给叶子节点
// 卡尔的理解方式比较复杂，不如直接理解为传入一个空的树，返回根据val创建的新节点即可
if (root == NULL)
{
TreeNode* node = new TreeNode(val);
return node;
}
// 卡尔的理解：在val节点作为叶子节点的左子节点时，当前节点的左指针指向val节点
// 在val节点作为叶子节点的右子节点时，当前节点的右指针指向val节点
if (val < root->val) root->left = insert(root->left, val);
if (val > root->val) root->right = insert(root->right, val);
return root;
}
卡尔相当于是从叶子节点开始，自下往上讲解递归法的原理。我的理解方式是从root节点开始，自上而下的理解递归的思路。我的理解方式要简单一些，有利于快速写出本题的递归版本的代码。本题也可以用迭代法，由于是二叉搜索树明确了搜索的方向，所以迭代法的代码也会比较简单。
看了代码随想录的讲解后，我独立写出了正统的迭代法的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28// 迭代写法
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
// 终止条件
if (root == NULL) return new TreeNode(val);
// 用cur节点作为当前遍历到的节点，用parent节点作为cur节点的父节点
// 因为最后是在叶子节点下插入新节点，因此cur节点必定会遍历到空节点，此时需要利用parent节点来指向新节点
TreeNode* parent = new TreeNode(0);
TreeNode* cur = root;
// cur == NULL时终止循环
while (cur)
{
// parent节点随着cur节点移动，但始终落后一步，因此parent节点是当前节点的上一个节点（父节点）
parent = cur;
// 根据二叉搜素树的有序性移动cur节点
if (val < cur->val) cur = cur->left;
else cur = cur->right;
}
// 最终在二叉搜索树的叶子节点下插入新节点，这就需要用到parent节点，因为cur节点已经为空
if (val < parent->val) parent->left = new TreeNode(val);
else parent->right = new TreeNode(val);
return root;
}
};
正统的迭代法采取的是双指针的思路，需要两个节点，一个是cur节点，其是遍历二叉搜索树时的当前节点。另一个是parent节点，其是当前节点的上一个节点（父节点）。
450.删除二叉搜索树中的节点
删除节点后，要保证二叉树依然是二叉搜索树。本题比较难，因为要修改二叉树的结构。删除节点后的二叉树结构不唯一，只要符合二叉搜索树的定义即可。下面开始分析可能的情况。
- 没找到要删除的节点
- 要删除的节点是叶子节点，左为空，右也为空（此时删除节点较为简单，因为不需要改变二叉树的结构）
- 要删除的节点左不为空，右为空。则让该节点的父节点直接指向该节点的左子节点
- 要删除的节点左为空，右不空。则让该节点的父节点直接指向该节点的右子节点
- 要删除的节点左不空，右不空。本情况最复杂，因为要大幅调整二叉搜索树的结构。拿以下二叉树为例：
例如删去节点7。让7的右子树继位，那么7的左子树应该放在右子树的哪里。7的左子树应该放在右子树中的左下角（右子树中的最小值）。让7的左子树继位也可以，原理相同。
接下来开始写代码（代码不多但不好理解）：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46// 不写cpp中需要释放内存的逻辑，只写核心代码
// 返回新二叉树的根节点
TreeNode* delete(TreeNode* root, int key)
{
// 终止条件
// 不需要遍历整个二叉树，找到要删除的点就是终止条件
// 找到要删除的点后就要删除该点，因此删除该点的操作在终止条件中
// 没找到要删除的节点/传入的二叉树为空
if (root == NULL) return NULL;
// 找到了要删除的节点
if (root->val == key)
{
// 要删除的节点是叶子节点，左为空，右也为空
// return NULL的意思是该节点的父节点指向NULL
if (root->left == NULL && root->right == NULL) return NULL;
// 要删除的节点左不为空，右为空
// 将要删除的节点的左孩子直接向上返回即可
else if (root->left && root->right == NULL) return root->left;
// 要删除的节点左为空，右不空
// 将要删除的节点的右孩子直接向上返回即可
else if (root->left == NULL && root->right) return root->right;
// 要删除的节点左不空，右不空
else
{
TreeNode* cur = root->right; // 要删除节点的右子树
while (cur->left) cur = cur->left; // 让cur指向右子树的左下角
cur->left = root->left; // 将要删除节点的左子树嫁接到右子树的左下角
// 移除要删除的节点，此时要删除的节点左为空右不为空，因为直接向上返回其右孩子即可
return root->right;
}
}
// 单层递归
// 二叉搜素树确定了搜索的方向
// root的左子树在删去节点后，左子树的新根节点嫁接到root->left上
if (key < root->val) root->left = delete(root->left, key);
// root的右子树在删去节点后，右子树的新根节点嫁接到root->left上
if (key > root->val) root->right = delete(root->right, key);
return root; // 看似没有处理root，但实际上已经在终止条件中处理了
}
上述代码不算复杂，但是很难想。注意：删除节点的操作是通过返回值来进行的，然后让本层递归的上一层去接住本层递归的返回值。本题也可以用迭代法实现。本题的进阶版本：在一般的二叉树中删除节点，更难。吃透本题即可。
本题精简的注释版本如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
// 终止条件，分为五种情况
// 情况1：找不到要删除的节点
if (root == NULL) return NULL;
if (root->val == key)
{
// 情况2，要删除的节点左右都为空
if (root->left == NULL && root->right == NULL) return NULL;
// 情况3，要删除的节点左为空右不空
else if (root->left == NULL && root->right) return root->right;
// 情况4，要删除的节点左不空右为空
else if (root->left && root->right == NULL) return root->left;
// 情况5，要删除的节点左不空右不空
else
{
TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
cur->left = root->left;
return root->right;
}
}
// 单层递归逻辑
if (root->val > key) root->left = deleteNode(root->left, key);
else root->right = deleteNode(root->right, key);
return root;
}
};
心得与备忘录
235. 二叉搜索树的最近公共祖先
- 本题和236的区别在于，本题的条件得到了强化，不仅是二叉树，而且是二叉搜索树。
- 由于二叉搜索树的方向性，本题不需要回溯，自上往下查找目标区间即可。
- 本题的核心思路：从上往下遍历二叉树，若当前节点的值大于p和q节点的值，则p和q的最近公共祖先在当前节点的左子树中，从当前节点开始向左遍历。若当前节点的值小于p和q节点的值，则p和q的最近公共祖先在当前节点的右子树中，从当前节点开始向右遍历。若当前节点的值在
[p->val, q->val]的范围内，则当前节点就是p和q的最近公共祖先。注意区间是左闭右闭，因为存在p为q的父节点的情况。 - 为什么当前节点的值在
[p->val, q->val]的范围内，就可以确定当前节点就是p和q的最近公共祖先，而不仅仅是一个普通的公共祖先？这个原因在于：当前节点的值>p->val，则说明p在当前节点的左子树中；当前节点的值<q->val，则说明q在当前节点的左子树中。因此若从当前节点开始向下移动到下一个节点处，那么不是错过p就是错过q。因此当前节点就是p和q的最近公共祖先。 - 因为二叉搜索树的有序性，本题的迭代写法也非常简单，甚至比递归解法更简单。
701.二叉搜索树中的插入操作
- 本题可以采用递归法和迭代法。但递归法的代码较为简单，因此推荐使用递归法。迭代法的代码略微复杂，但采用的双指针思路也非常清晰，因此也可以掌握迭代法。
- 插入新节点的方式有多种，得到的二叉搜索树不唯一。但必然可以在二叉搜索树的叶子节点处插入新的节点。因此不用改变二叉搜索树的结构，就可以实现插入操作。这是本题简单易解的根本所在。
本题递归法的思路：
- 递归函数的返回值：返回插入新节点后二叉搜索树的根节点。也可以返回空，但那样写比较麻烦。
- 终止条件：root节点为空时，说明输入的二叉树为空，因此直接返回val节点即可。
- 单层递归逻辑：若
val > root->val，说明val节点应该被插入在root节点的右子树中，因此有root->right = insert(root->right, val)（insert(root->right, val)返回了root的右子树在插入新节点后的头节点，用root的右节点指向该头节点即可）。若val < root->val，说明val节点应该被插入在root节点的左子树中，因此有root->left = insert(root->left, val)。最终返回root即可。
卡尔相当于是从叶子节点开始，自下往上讲解递归法的原理。我的理解方式是从root节点开始，自上而下的理解递归的思路。我的理解方式要简单一些，有利于快速写出本题的递归版本的代码。
本题的迭代写法思路也非常清晰。迭代法采取的是双指针的思路，需要两个节点，一个是cur节点，其是遍历二叉搜索树时的当前节点。另一个是parent节点，其是当前节点的上一个节点（父节点）。我在初次尝试中实现的迭代法代码复杂且由于要考虑多种情况，非常容易写错。因此建议如果要写迭代法，就采用基于双指针思路的迭代法。
450.删除二叉搜索树中的节点
本题相比于在二叉搜索树中插入节点，复杂得多，原因是删除二叉搜索树中的节点且保持该二叉树仍为二叉搜索树，会改变二叉搜索树原本的结构。
本题的第一个难点在于分析出删除一个节点的五种情况。
找不到要删除的节点
要删除的节点的左右子节点均为空
要删除的节点的左空右不空
要删除的节点的左不空右空
要删除的节点的左右均不空
由于在终止条件中要找到需要删除的节点，因此删除节点的操作也在终止条件中完成。
本题的第二个难点在于实现第五种情况的代码。我直接附上相应的代码并进行解释：
1
2
3
4TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
cur->left = root->left;
return root->right;先找到要删除的节点root，然后让cur指针指向root的右子节点。接着用cur遍历root的右子树，直到cur指向右子树的左下角。将root的左子树嫁接到右子树的左下角，最后返回root的右子节点。以root的右子节点为根节点的二叉树就是一棵二叉搜索树。可以举例子画图理解上述构造二叉搜索树的操作。
本题的基本原理在于：删除节点的操作是通过返回值进行的，然后让本层递归的上一层去接住本层递归的返回值。
- 删除一般的二叉树中的节点要采用另外的算法，因此不要求掌握。
- 本题也有迭代写法，需要用到双指针算法，代码也更加复杂，因此不要求掌握。
- 按理来说，cpp中需要显式地释放被删除节点占用的内存。但不释放也不会对代码的正常运行造成影响。