今天的题都是二叉搜索树相关，涉及查找、插入和删除。重点是在插入、删除时将递归返回值设置为父节点的左/右子节点，其返回值就是处理结束后子树的根节点。难度上，删除 > 插入 > 查找。
第1题（235. 二叉搜索树的最近公共祖先）相比day 21中最后一题（236. 二叉树的最近公共祖先）要容易很多。因为二叉搜索树是有序的，所以查找方向是确定的，那么就不需要向上回溯，只需要按照确定的方向向下查找。首先需要明确如果某个节点的val大小在p和q之间，那么它就是p和q的最小公共祖先了（因为此时p和q位于它的两侧）。如果当前节点为空则说明未找到（虽然在这一题中没用，因为题目说明一定会找到），而如果找到p或q，就返回当前节点（p或q）。如果找到了p或q，说明p和q是祖先/子孙的关系。否则在p和q位于左右两侧的时候，就已经返回当前节点作为答案了，不会进行到找到p或q这一步。又因为是前序遍历，所以首先被找到的一定是两者中的祖先，也就是答案。不是上面2种情况的话，再判断当前节点与p、q的val的大小关系，如果都比当前节点小，就递归向左查找，反之向右查找。而如果位于p、q之间，就如一开始说的，返回当前节点。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (root == nullptr) {
return nullptr;
}
if (root == p || root == q) {
return root;
}
if (p->val < root->val && q->val < root->val){
return lowestCommonAncestor(root->left, p, q);
}
if (p->val > root->val && q->val > root->val) {
return lowestCommonAncestor(root->right, p, q);
}
return root;
}
};迭代解法比较简单，与递归法的思路一致，只是将递归变为了当前节点的更新。不断根据val大小更新当前节点为左节点或右节点，直到找到最小公共祖先即可。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
while (root != nullptr) {
if (root == p || root == q) {
return root;
}
if (p->val < root->val && q->val < root->val){
root = root->left;
}
else if (p->val > root->val && q->val > root->val) {
root = root->right;
}
else {
return root;
}
}
return nullptr;
}
};第2题（701.二叉搜索树中的插入操作）的递归法自己AC的思路是判断当前节点是否可以插入，插入条件为应该插入左边且左节点为空，或者应该插入右节点且右节点为空。如满足则插入并返回，如不满足则根据val大小向左或向右递归。
class Solution {
public:
void insertNode(TreeNode *cur, int val) {
if (cur->left == nullptr && val < cur->val) {
TreeNode *node = new TreeNode(val);
cur->left = node;
return;
}
if (cur->right == nullptr && val > cur->val) {
TreeNode *node = new TreeNode(val);
cur->right = node;
return;
}
if (val < cur->val) {
insertNode(cur->left, val);
}
else {
insertNode(cur->right, val);
}
return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
root = new TreeNode(val);
return root;
}
insertNode(root, val);
return root;
}
};需要注意题目中待被插入的树节点数有可能为0，即树是空树，所以要对这种情况做特殊处理。
题解的递归思路是无论如何都插入到叶子节点下面，所以递归出口是查找到空节点后就建立待插入节点并将其返回。而在递归处理逻辑中，根据val的大小，对左或右节点进行递归，并将其返回值赋给左或右节点。这样一来，对于非叶子节点的这个赋值是等于没有操作的，只有对叶子节点，才会插入新建的节点。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode *node = new TreeNode(val);
return node;
}
if (val < root->val) {
root->left= insertIntoBST(root->left, val);
}
else {
root->right = insertIntoBST(root->right, val);
}
return root;
}
};另外，也可以使用无返回值，找到叶子节点后直接插入的方法。但因为从二叉树节点无法获取其父节点，所以需要一个全局变量来保存父节点。
class Solution {
public:
TreeNode *parent;
void insertNode(TreeNode *cur, int val) {
if (cur == nullptr) {
TreeNode *node = new TreeNode(val);
if (val < parent->val) {
parent->left = node;
}
else {
parent->right = node;
}
return;
}
parent = cur;
if (val < cur->val) {
insertNode(cur->left, val);
}
else {
insertNode(cur->right, val);
}
return;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == nullptr) {
TreeNode *node = new TreeNode(val);
return node;
}
parent = root;
insertNode(root, val);
return root;
}
};迭代法沿用使用parent记录父节点的思路，不断向下查找，直到cur为空节点，parent为叶子节点，再对parent插入。
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
TreeNode *node = new TreeNode(val);
if (root == nullptr) {
return node;
}
TreeNode *cur = root, *parent;
while (cur != nullptr) {
parent = cur;
if (val < cur->val) {
cur = cur->left;
}
else {
cur = cur->right;
}
}
if (val < parent->val) {
parent->left = node;
}
else {
parent->right = node;
}
return root;
}
};第3题（450. 删除二叉搜索树中的节点）的递归解法自己AC的思路在遇到空节点时返回；遇到非空且val与目标val不相等的节点时，递归向左或向右查找（同第2题一样）并将返回值赋给左/右节点；而如果查找到目标节点，则分几种情况处理：
- 目标节点为叶子节点，则返回nullptr。相当于用nullptr替换目标节点；
- 目标节点有且仅有一个子节点，则返回其子节点。相当于用其存在的子节点对应的树替换目标节点；
- 目标节点有2个子节点时：（1）右子节点为叶子节点时，用右子节点替换目标节点；（2）右子节点不是叶子节点时，用右子节点对应树的最左节点替换目标节点。
最后返回当前节点。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val == key) {
// 目标节点左右两边中，一边（2）或两边为空（1）时
if (root->left == nullptr) {
return root->right;
}
if (root->right == nullptr) {
return root->left;
}
// 两边都不为空时（3）
TreeNode *cur = root->right, *parent = root;
while (cur->left != nullptr) {
parent = cur;
cur = cur->left;
}
// 右边只有一个节点时，用其替换目标节点（3.1）
if (parent != root) {
parent->left = cur->right;
cur->left = root->left;
cur->right = root->right;
}
// 右边不止一个节点时，用右子树的最左节点替换目标节点（3.2）
else {
cur->left = root->left;
}
return cur;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
}
else if (key > root->val) {
root->right = deleteNode(root->right, key);
}
return root;
}
};题解的递归解法则更简单些，将上面第3种情况的处理方式统一为：
- 将目标节点的左子树放在右子树的最左节点的左节点上；
- 用更新后的右子树替换目标节点。
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
if (root->val == key) {
// 目标节点左右两边中，一边（2）或两边为空（1）时
if (root->left == nullptr) {
return root->right;
}
if (root->right == nullptr) {
return root->left;
}
// 两边都不为空时（3）
TreeNode *cur = root->right;
while (cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left;
return root->right;
}
if (key < root->val) {
root->left = deleteNode(root->left, key);
}
else if (key > root->val) {
root->right = deleteNode(root->right, key);
}
return root;
}
};迭代法自己的实现是沿用递归法的处理思路，但相比较递归法要麻烦很多，因为要处理目标节点是root的情况。这种情况在递归法中的每种情形种都可能出现，都要做对应处理。另外由于目标节点是父节点的左子节点还是右子节点这一信息也需要保存，并做对应不同处理：
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
TreeNode *cur = root, *parent;
bool isLeft;
while (cur != nullptr) {
if (cur->val == key) {
// 目标节点左右两边中，一边（2）或两边为空（1）时
if (cur->left == nullptr) {
if (cur == root) {
return root->right;
}
if (isLeft) {
parent->left = cur->right;
}
else {
parent->right = cur->right;
}
return root;
}
if (cur->right == nullptr) {
if (cur == root) {
return root->left;
}
if (isLeft) {
parent->left = cur->left;
}
else {
parent->right = cur->left;
}
return root;
}
// 两边都不为空时（3）
TreeNode *mostLeft = cur->right;
while (mostLeft->left != nullptr) {
mostLeft = mostLeft->left;
}
mostLeft->left = cur->left;
if (cur == root) {
return root->right;
}
if (isLeft) {
parent->left = cur->right;
}
else {
parent->right = cur->right;
}
return root;
}
if (key < cur->val) {
parent = cur;
isLeft = true;
cur = cur->left;
}
else if (key > cur->val) {
parent = cur;
isLeft = false;
cur = cur->right;
}
}
return root;
}
};实现过程中多次因为目标节点是root，且root是叶子节点，及不是叶子节点的情况而出错。
题解则将删除一个节点的过程封装为了函数，从而避免了自己实现方法中多出来的各种判断和特殊情况。删除节点的函数返回删除后，需要调整部分的树的根节点。这样一来，如果目标节点是根节点，主函数直接返回删除节点函数的返回值即可；否则就将删除节点函数的返回值赋给parent节点的左/右节点，再返回root。
class Solution {
public:
TreeNode* deleteOneNode(TreeNode *target) {
if (target->left == nullptr) {
return target->right;
}
if (target->right == nullptr) {
return target->left;
}
TreeNode *rightMostLeft = target->right;
while (rightMostLeft->left != nullptr) {
rightMostLeft = rightMostLeft->left;
}
rightMostLeft->left = target->left;
return target->right;
}
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) {
return nullptr;
}
TreeNode *cur = root, *parent = nullptr;
while (cur != nullptr) {
if (cur->val == key) {
break;
}
if (key < cur->val) {
parent = cur;
cur = cur->left;
}
else if (key > cur->val) {
parent = cur;
cur = cur->right;
}
}
if (cur == root) {
return deleteOneNode(cur);
}
if (parent->left != nullptr && parent->left->val == key) {
parent->left = deleteOneNode(cur);
}
if (parent->right != nullptr && parent->right->val == key) {
parent->right = deleteOneNode(cur);
}
return root;
}
};另外，对于一般二叉树（非二叉搜索树）节点的删除，使用我自己实现的递归解法思路即可。