摘要
- 二叉搜索樹(shù)兩個(gè)節(jié)點(diǎn)的最近公共祖先的值在兩個(gè)節(jié)點(diǎn)之間记罚，自上向下遍歷次泽，遇到的第一個(gè)值在兩個(gè)目標(biāo)節(jié)點(diǎn)的值的節(jié)點(diǎn)即為最近公共祖先
- 二叉搜索樹(shù)的插入变秦，可以直接在葉節(jié)點(diǎn)處插入成榜，但這會(huì)造成二叉搜索樹(shù)的不平衡，有更好的插入方法
- 二叉搜索樹(shù)的節(jié)點(diǎn)的刪除需要調(diào)整樹(shù)的結(jié)構(gòu)來(lái)保證刪除節(jié)點(diǎn)后的樹(shù)仍然是二叉搜索樹(shù)蹦玫，所以要分情況討論赎婚。
LeetCode235 二叉搜索樹(shù)的最近公共祖先
- 從二叉搜索樹(shù)的定義出發(fā)，先復(fù)習(xí)二叉搜索樹(shù)的定義
- 二叉搜索樹(shù)是一個(gè)有序樹(shù)：
- 若它的左子樹(shù)不空樱溉，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值挣输；
- 若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值福贞；
- 它的左撩嚼、右子樹(shù)也分別為二叉搜索樹(shù)
- 二叉搜索樹(shù)是一個(gè)有序樹(shù)：
- 如果一個(gè)節(jié)點(diǎn)是
p和q的公共祖先，那p和q的公共祖先的值一定在p和q之間：。注意是左閉右閉區(qū)間完丽，一個(gè)節(jié)點(diǎn)的值也可以是它自己的祖先恋技。
- 但問(wèn)題在于，值在
p和q之間的節(jié)點(diǎn)逻族，不一定是p和q的公共祖先蜻底。比如下圖的樹(shù)
image.png
- 從上到下，假設(shè)我們首先找到了
5瓷耙，5在1和9之間- 首先朱躺，
5在1和9之間刁赖，根據(jù)二叉搜索樹(shù)的定義搁痛，此時(shí)1在5的左子樹(shù)，9在5的右子樹(shù)宇弛。 - 如果
5不是1和9的最近公共祖先鸡典，那我們應(yīng)該繼續(xù)向下找1和9深度更大的公共祖先。 - 可是枪芒，
5的左孩子肯定不是q的祖先彻况，5的右孩子肯定不是p的祖先。既然再向下已經(jīng)不能找到p和q的共同祖先了舅踪，那么5就是p和q的最近公共祖先纽甘。
- 首先朱躺，
- 尋找兩個(gè)節(jié)點(diǎn)的最近公共祖先能充分利用二叉搜索樹(shù)的性質(zhì)：
- 當(dāng)前節(jié)點(diǎn)的值小于
p和q中的最小值時(shí)，p和q都在當(dāng)前節(jié)點(diǎn)的右子樹(shù)抽碌；所以此時(shí)應(yīng)該訪(fǎng)問(wèn)左子樹(shù)悍赢。 - 當(dāng)前節(jié)點(diǎn)的值大于
p和q中的最大值時(shí)，p和q都在當(dāng)前節(jié)點(diǎn)的左子樹(shù)货徙；所以此時(shí)應(yīng)該訪(fǎng)問(wèn)右子樹(shù)左权。
- 當(dāng)前節(jié)點(diǎn)的值小于
遞歸法代碼如下
class Solution {
public:
TreeNode* search(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root) return nullptr;// 沒(méi)找到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 二叉搜索樹(shù)中的插入操作
- 初見(jiàn)題目時(shí)的想法：要在二叉搜索樹(shù)中進(jìn)行插入操作，首先要找到合適的插入位置痴颊，確保插入一個(gè)節(jié)點(diǎn)后的樹(shù)還是二叉搜索樹(shù)赏迟。所以，可以根據(jù)要插入的值蠢棱，先在二叉搜索樹(shù)中進(jìn)行搜索锌杀，在遇到空節(jié)點(diǎn)時(shí)，將要插入的值放在空節(jié)點(diǎn)的位置泻仙。
題解代碼如下（迭代法）
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;
}
};
遞歸法實(shí)現(xiàn)如下
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;
}
};
- 如果要求二叉搜索樹(shù)是平衡的話(huà)糕再，以上這種簡(jiǎn)單插入是不可行的，待以后遇到平衡二叉搜索樹(shù)再繼續(xù)總結(jié)饰豺。
LeetCode450 刪除二叉搜索樹(shù)的節(jié)點(diǎn)
-
在二叉搜索樹(shù)中刪除節(jié)點(diǎn)亿鲜，首先要做以下兩步：
- 找到要?jiǎng)h除的節(jié)點(diǎn)
- 刪除該節(jié)點(diǎn)
-
然后調(diào)整樹(shù)的結(jié)構(gòu)，使得刪除目標(biāo)節(jié)點(diǎn)后的二叉樹(shù)仍然是二叉搜索樹(shù)。這就需要分情況討論被刪除的節(jié)點(diǎn)的位置：
- 沒(méi)找到被刪除的節(jié)點(diǎn)
- 如果被刪除的節(jié)點(diǎn)是葉節(jié)點(diǎn)蒿柳，直接刪除
- 如果被刪除的節(jié)點(diǎn)有左子樹(shù)但沒(méi)有右子樹(shù)饶套，將左孩子接在被刪除的節(jié)點(diǎn)的位置上
- 如果被刪除的節(jié)點(diǎn)有右子樹(shù)但沒(méi)有左子樹(shù)，將右孩子接在被刪除的節(jié)點(diǎn)的位置上
- 如果被刪除的節(jié)點(diǎn)既有左子樹(shù)垒探，又有右子樹(shù)妓蛮，就需要對(duì)樹(shù)的結(jié)構(gòu)進(jìn)行調(diào)整，一種比較簡(jiǎn)單的方法是圾叼，將被刪除的節(jié)點(diǎn)的左孩子接在右子樹(shù)的最小值的左孩子上蛤克，這樣可以保證刪除節(jié)點(diǎn)后的樹(shù)仍然是二叉搜索樹(shù)。
-
遞歸法實(shí)現(xiàn)思路：
傳入的參數(shù)和返回值：傳入當(dāng)前子樹(shù)的根節(jié)點(diǎn)和要?jiǎng)h除的
key值夷蚊。樹(shù)的節(jié)點(diǎn)刪除類(lèi)似鏈表操作构挤，需要更改節(jié)點(diǎn)left或right，所以需要返回刪除后當(dāng)前子樹(shù)根節(jié)點(diǎn)的新的left和right惕鼓。遞歸的終止條件：一是沒(méi)找到
key值筋现；二是找到了key要進(jìn)行刪除，對(duì)節(jié)點(diǎn)的刪除操作要在遞歸終止前進(jìn)行箱歧。單層遞歸的邏輯：判斷當(dāng)前節(jié)點(diǎn)的值是否為要?jiǎng)h除的
key矾飞，如果是，則進(jìn)行刪除操作呀邢，如果不是洒沦，則繼續(xù)向下找要?jiǎng)h除的節(jié)點(diǎn)，且更新當(dāng)前節(jié)點(diǎn)的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) {
// 葉節(jié)點(diǎn)申眼，直接刪除
delete root;
return nullptr;
}
else if (root->left && !root->right) {
// 有左子樹(shù)，返回左孩子输钩，接到上一層
TreeNode* left = root->left;
delete root;
return left;
}
else if (!root->left && root->right) {
// 有右子樹(shù)豺型，返回右孩子，接到上一層
TreeNode* right = root->right;
delete root;
return right;
}
else {
// 既有左子樹(shù)又有右子樹(shù)
// 1. 找右子樹(shù)的最小值
TreeNode* cur = root->right;
while (cur->left) cur = cur->left;
// 將被刪除的節(jié)點(diǎn)的左孩子接在右子樹(shù)的最小值上
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);
}
};
- 當(dāng)被刪除的節(jié)點(diǎn)的左右子樹(shù)都不為空時(shí)买乃，另外一種方法是先交換當(dāng)前節(jié)點(diǎn)的值和右子樹(shù)最小值姻氨，然后再向右子樹(shù)去找要?jiǎng)h除的值。
- 交換當(dāng)前節(jié)點(diǎn)的值和右子樹(shù)的最小值剪验，可能會(huì)使得當(dāng)前子樹(shù)不是二叉搜索樹(shù)肴焊。但由于當(dāng)前節(jié)點(diǎn)值小于右子樹(shù)的最小值（二叉搜索樹(shù)的定義），所以交換后的右子樹(shù)仍然是二叉搜索樹(shù)功戚。
- 所以只需要再向右子樹(shù)查找一次要被刪除的節(jié)點(diǎn)娶眷，并刪除它即可。
- 此時(shí)要?jiǎng)h除的節(jié)點(diǎn)不再是左右子樹(shù)都不為空的情況啸臀，刪除節(jié)點(diǎn)的操作會(huì)變得簡(jiǎn)單届宠。
例子如下烁落，假如我們要?jiǎng)h除的key為7
- 第一次找到要?jiǎng)h除的節(jié)點(diǎn)
7，我們讓它的值與右子樹(shù)的最小值8交換
第一次找到要?jiǎng)h除的節(jié)點(diǎn)
- 交換后的樹(shù)如下圖豌注，顯然此時(shí)以
root為根節(jié)點(diǎn)的子樹(shù)不是二叉搜素樹(shù)（7 < 8伤塌，7 卻在 8 的右子樹(shù)里），所以我們要手動(dòng)指定搜索方向?yàn)橄蛴易訕?shù)搜索轧铁。
交換要?jiǎng)h除的節(jié)點(diǎn)的值和右子樹(shù)“左下角”節(jié)點(diǎn)的值
- 第二次找到
7每聪，此時(shí)要?jiǎng)h除的節(jié)點(diǎn)的左子樹(shù)一定為空（如果左子樹(shù)不為空，說(shuō)明在右子樹(shù)里還有比交換前的當(dāng)前節(jié)點(diǎn)的值更小的節(jié)點(diǎn)齿风，即在本例子中還有比 8 更小的值药薯，這和第一步中與右子樹(shù)的最小值是矛盾的）。既然左子樹(shù)一定為空救斑，要么是刪除葉節(jié)點(diǎn)（右子樹(shù)也為空）童本，要么是將右子樹(shù)接上，都是比較簡(jiǎn)單的刪除操作系谐。
第二次找到要?jiǎng)h除的節(jié)點(diǎn)巾陕，將其刪除
完整題解代碼如下
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);
}
};
