摘要
- 二叉搜索树两个节点的最近公共祖先的值在两个节点之间，自上向下遍历，遇到的第一个值在两个目标节点的值的节点即为最近公共祖先
- 二叉搜索树的插入，可以直接在叶节点处插入，但这会造成二叉搜索树的不平衡，有更好的插入方法
- 二叉搜索树的节点的删除需要调整树的结构来保证删除节点后的树仍然是二叉搜索树，所以要分情况讨论。
LeetCode235 二叉搜索树的最近公共祖先
- 从二叉搜索树的定义出发，先复习二叉搜索树的定义
- 二叉搜索树是一个有序树：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉搜索树
- 二叉搜索树是一个有序树：
- 如果一个节点是
p和q的公共祖先，那p和q的公共祖先的值一定在p和q之间：。注意是左闭右闭区间，一个节点的值也可以是它自己的祖先。
- 但问题在于，值在
p和q之间的节点，不一定是p和q的公共祖先。比如下图的树
image.png
- 从上到下，假设我们首先找到了
5，5在1和9之间- 首先，
5在1和9之间，根据二叉搜索树的定义，此时1在5的左子树，9在5的右子树。 - 如果
5不是1和9的最近公共祖先，那我们应该继续向下找1和9深度更大的公共祖先。 - 可是，
5的左孩子肯定不是q的祖先，5的右孩子肯定不是p的祖先。既然再向下已经不能找到p和q的共同祖先了，那么5就是p和q的最近公共祖先。
- 首先，
- 寻找两个节点的最近公共祖先能充分利用二叉搜索树的性质：
- 当前节点的值小于
p和q中的最小值时，p和q都在当前节点的右子树；所以此时应该访问左子树。 - 当前节点的值大于
p和q中的最大值时，p和q都在当前节点的左子树；所以此时应该访问右子树。
- 当前节点的值小于
递归法代码如下
class Solution {
public:
TreeNode* search(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;// 没找到p, q
if (root->val > p->val && root->val > q->val) {//[p, q] < root
TreeNode* left = search(root->left, p, q);
if (left) return left;
}
if (root->val < p->val && root->val < q->val) {// root < [p, q]
TreeNode* right = search(root->right, p, q);
if (right) return right;
}
return root;// root ∈ [p, q]
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return search(root, p, q);
}
};
迭代法代码如下
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
TreeNode* cur = root;
while (cur) {
if (p->val < cur->val && q->val < cur->val) {
cur = cur->left;
continue;
}
if (p->val > cur->val && q->val > cur->val) {
cur = cur->right;
continue;
}
return cur;
}
return cur;
}
};
LeetCode701 二叉搜索树中的插入操作
- 初见题目时的想法：要在二叉搜索树中进行插入操作，首先要找到合适的插入位置，确保插入一个节点后的树还是二叉搜索树。所以，可以根据要插入的值，先在二叉搜索树中进行搜索，在遇到空节点时，将要插入的值放在空节点的位置。
题解代码如下（迭代法）
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
TreeNode* cur = root;
while (cur) {
if (val < cur->val) {
if (cur->left) cur = cur->left;
else {
cur->left = new TreeNode(val);
break;
}
}
if (val > cur->val) {
if (cur->right) cur = cur->right;
else {
cur->right = new TreeNode(val);
break;
}
}
}
return root;
}
};
递归法实现如下
class Solution {
public:
TreeNode* insert(TreeNode* cur, int& val) {
if (!cur) {
cur = new TreeNode(val);
return cur;
}
if (val < cur->val) cur->left = insert(cur->left, val);
if (val > cur->val) cur->right = insert(cur->right, val);
return cur;
}
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (!root) return new TreeNode(val);
insert(root, val);
return root;
}
};
- 如果要求二叉搜索树是平衡的话，以上这种简单插入是不可行的，待以后遇到平衡二叉搜索树再继续总结。
LeetCode450 删除二叉搜索树的节点
-
在二叉搜索树中删除节点，首先要做以下两步：
- 找到要删除的节点
- 删除该节点
-
然后调整树的结构，使得删除目标节点后的二叉树仍然是二叉搜索树。这就需要分情况讨论被删除的节点的位置：
- 没找到被删除的节点
- 如果被删除的节点是叶节点，直接删除
- 如果被删除的节点有左子树但没有右子树，将左孩子接在被删除的节点的位置上
- 如果被删除的节点有右子树但没有左子树，将右孩子接在被删除的节点的位置上
- 如果被删除的节点既有左子树，又有右子树，就需要对树的结构进行调整，一种比较简单的方法是，将被删除的节点的左孩子接在右子树的最小值的左孩子上，这样可以保证删除节点后的树仍然是二叉搜索树。
-
递归法实现思路：
传入的参数和返回值：传入当前子树的根节点和要删除的
key值。树的节点删除类似链表操作，需要更改节点left或right，所以需要返回删除后当前子树根节点的新的left和right。递归的终止条件：一是没找到
key值；二是找到了key要进行删除，对节点的删除操作要在递归终止前进行。单层递归的逻辑：判断当前节点的值是否为要删除的
key，如果是，则进行删除操作，如果不是，则继续向下找要删除的节点，且更新当前节点的left和right。
完整题解代码如下
/**
* 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* deleteBSTNode(TreeNode* root, int& key) {
if (!root) return nullptr;
if (key == root->val) {
if (!root->left && !root->right) {
// 叶节点，直接删除
delete root;
return nullptr;
}
else if (root->left && !root->right) {
// 有左子树，返回左孩子，接到上一层
TreeNode* left = root->left;
delete root;
return left;
}
else if (!root->left && root->right) {
// 有右子树，返回右孩子，接到上一层
TreeNode* right = root->right;
delete root;
return right;
}
else {
// 既有左子树又有右子树
// 1. 找右子树的最小值
TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
// 将被删除的节点的左孩子接在右子树的最小值上
cur->left = root->left;
TreeNode* right = root->right;
delete root;
return right;
}
}
if (key < root->val) root->left = deleteBSTNode(root->left, key);
if (key > root->val) root->right = deleteBSTNode(root->right, key);
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
return deleteBSTNode(root, key);
}
};
- 当被删除的节点的左右子树都不为空时，另外一种方法是先交换当前节点的值和右子树最小值，然后再向右子树去找要删除的值。
- 交换当前节点的值和右子树的最小值，可能会使得当前子树不是二叉搜索树。但由于当前节点值小于右子树的最小值（二叉搜索树的定义），所以交换后的右子树仍然是二叉搜索树。
- 所以只需要再向右子树查找一次要被删除的节点，并删除它即可。
- 此时要删除的节点不再是左右子树都不为空的情况，删除节点的操作会变得简单。
例子如下，假如我们要删除的key为7
- 第一次找到要删除的节点
7，我们让它的值与右子树的最小值8交换
第一次找到要删除的节点
- 交换后的树如下图，显然此时以
root为根节点的子树不是二叉搜素树（7 < 8，7 却在 8 的右子树里），所以我们要手动指定搜索方向为向右子树搜索。
交换要删除的节点的值和右子树“左下角”节点的值
- 第二次找到
7，此时要删除的节点的左子树一定为空（如果左子树不为空，说明在右子树里还有比交换前的当前节点的值更小的节点，即在本例子中还有比 8 更小的值，这和第一步中与右子树的最小值是矛盾的）。既然左子树一定为空，要么是删除叶节点（右子树也为空），要么是将右子树接上，都是比较简单的删除操作。
第二次找到要删除的节点，将其删除
完整题解代码如下
class Solution {
public:
TreeNode* deleteBSTNode(TreeNode* root, int& key) {
if (!root) return nullptr;
if (key == root->val) {
if (!root->left && !root->right) {
delete root;
return nullptr;
}
else if (root->left && !root->right) {
TreeNode* left = root->left;
delete root;
return left;
}
else if (!root->left && root->right) {
TreeNode* right = root->right;
delete root;
return right;
}
else {
TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
swap(root->val, cur->val);
root->right = deleteBSTNode(root->right, key);
return root;
}
}
if (key < root->val) root->left = deleteBSTNode(root->left, key);
if (key > root->val) root->right = deleteBSTNode(root->right, key);
return root;
}
TreeNode* deleteNode(TreeNode* root, int key) {
return deleteBSTNode(root, key);
}
};
