235. 二叉搜索樹的最近公共祖先
題目鏈接
解題思路：討論 中節(jié)點(diǎn) > p && 中節(jié)點(diǎn) < q 或者 中節(jié)點(diǎn) > q && 中節(jié)點(diǎn) < p，其余的情況的最近公共祖先就是根節(jié)點(diǎn)。
使用遞歸三部曲
- 確定遞歸函數(shù)返回值以及參數(shù)
參數(shù)就是當(dāng)前節(jié)點(diǎn)，以及兩個(gè)結(jié)點(diǎn) p、q。
返回值是要返回最近公共祖先，所以是TreeNode * 。
代碼如下：
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q)
- 確定終止條件
遇到空返回就可以了，代碼如下：
if (cur == NULL) return cur;
其實(shí)都不需要這個(gè)終止條件，因?yàn)轭}目中說了p、q 為不同節(jié)點(diǎn)且均存在于給定的二叉搜索樹中。也就是說一定會(huì)找到公共祖先的，所以并不存在遇到空的情況。
- 確定單層遞歸的邏輯
在遍歷二叉搜索樹的時(shí)候就是尋找區(qū)間[p->val, q->val]（注意這里是左閉右閉）
那么如果 cur->val 大于 p->val，同時(shí) cur->val 大于q->val，那么就應(yīng)該向左遍歷（說明目標(biāo)區(qū)間在左子樹上）。
需要注意的是此時(shí)不知道p和q誰大，所以兩個(gè)都要判斷
代碼如下：
if (cur->val > p->val && cur->val > q->val) {
TreeNode* left = traversal(cur->left, p, q);
if (left != NULL) {
return left;
}
}
代碼如下：
class Solution {
private:
TreeNode* traversal(TreeNode* cur, TreeNode* p, TreeNode* q) {
if (cur == NULL) return cur;
// 中
if (cur->val > p->val && cur->val > q->val) { // 左
TreeNode* left = traversal(cur->left, p, q);
if (left != NULL) {
return left;
}
}
if (cur->val < p->val && cur->val < q->val) { // 右
TreeNode* right = traversal(cur->right, p, q);
if (right != NULL) {
return right;
}
}
return cur; // 如果是一左一右，則cur就是最近公共祖先
}
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
return traversal(root, p, q);
}
};
701.二叉搜索樹中的插入操作
題目鏈接
解題思路：
遞歸三部曲：
- 確定遞歸函數(shù)參數(shù)以及返回值
參數(shù)就是根節(jié)點(diǎn)指針，以及要插入元素，這里遞歸函數(shù)要不要有返回值呢？
可以有，也可以沒有，但遞歸函數(shù)如果沒有返回值的話，實(shí)現(xiàn)是比較麻煩的，下面也會(huì)給出其具體實(shí)現(xiàn)代碼。
有返回值的話，可以利用返回值完成新加入的節(jié)點(diǎn)與其父節(jié)點(diǎn)的賦值操作。
遞歸函數(shù)的返回類型為節(jié)點(diǎn)類型TreeNode * 。
代碼如下：
TreeNode* insertIntoBST(TreeNode* root, int val)
- 確定終止條件
終止條件就是找到遍歷的節(jié)點(diǎn)為null的時(shí)候，就是要插入節(jié)點(diǎn)的位置了，并把插入的節(jié)點(diǎn)返回。
代碼如下：
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
這里把添加的節(jié)點(diǎn)返回給上一層，就完成了父子節(jié)點(diǎn)的賦值操作了，詳細(xì)再往下看。
- 確定單層遞歸的邏輯
搜索樹是有方向了，可以根據(jù)插入元素的數(shù)值，決定遞歸方向。
代碼如下：
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
到這里，大家應(yīng)該能感受到，如何通過遞歸函數(shù)返回值完成了新加入節(jié)點(diǎn)的父子關(guān)系賦值操作了，下一層將加入節(jié)點(diǎn)返回，本層用root->left或者root->right將其接住。
整體代碼如下：
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) {
TreeNode* node = new TreeNode(val);
return node;
}
if (root->val > val) root->left = insertIntoBST(root->left, val);
if (root->val < val) root->right = insertIntoBST(root->right, val);
return root;
}
};
450.刪除二叉搜索樹中的節(jié)點(diǎn)
題目鏈接
解題思路：
遞歸三部曲：
- 確定遞歸函數(shù)參數(shù)以及返回值
說到遞歸函數(shù)的返回值，在上一題中通過遞歸返回值來加入新節(jié)點(diǎn)， 這里也可以通過遞歸返回值刪除節(jié)點(diǎn)。
代碼如下：
TreeNode* deleteNode(TreeNode* root, int key)
- 確定終止條件
遇到空返回，其實(shí)這也說明沒找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了
if (root == nullptr) return root;
- 確定單層遞歸的邏輯
這里就把二叉搜索樹中刪除節(jié)點(diǎn)遇到的情況都搞清楚。
有以下五種情況：
- 第一種情況：沒找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了
- 找到刪除的節(jié)點(diǎn)
第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn)
第三種情況：刪除節(jié)點(diǎn)的左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位，返回右孩子為根節(jié)點(diǎn)
第四種情況：刪除節(jié)點(diǎn)的右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn)
第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹頭結(jié)點(diǎn)（左孩子）放到刪除節(jié)點(diǎn)的右子樹的最左面節(jié)點(diǎn)的左孩子上，返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。
代碼如下：
if (root->val == key) {
// 第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn)
// 第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 ，返回右孩子為根節(jié)點(diǎn)
if (root->left == nullptr) return root->right;
// 第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn)
else if (root->right == nullptr) return root->left;
// 第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹放到刪除節(jié)點(diǎn)的右子樹的最左面節(jié)點(diǎn)的左孩子的位置
// 并返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。
else {
TreeNode* cur = root->right; // 找右子樹最左面的節(jié)點(diǎn)
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要?jiǎng)h除的節(jié)點(diǎn)（root）左子樹放在cur的左孩子的位置
TreeNode* tmp = root; // 把root節(jié)點(diǎn)保存一下，下面來刪除
root = root->right; // 返回舊root的右孩子作為新root
delete tmp; // 釋放節(jié)點(diǎn)內(nèi)存（這里不寫也可以，但C++最好手動(dòng)釋放一下吧）
return root;
}
}
這里相當(dāng)于把新的節(jié)點(diǎn)返回給上一層，上一層就要用 root->left 或者 root->right接住，代碼如下：文章來源：http://www.zghlxwxcb.cn/news/detail-482917.html
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-482917.html
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
if (root == nullptr) return root; // 第一種情況：沒找到刪除的節(jié)點(diǎn)，遍歷到空節(jié)點(diǎn)直接返回了
if (root->val == key) {
// 第二種情況：左右孩子都為空（葉子節(jié)點(diǎn)），直接刪除節(jié)點(diǎn)， 返回NULL為根節(jié)點(diǎn)
if (root->left == nullptr && root->right == nullptr) {
///! 內(nèi)存釋放
delete root;
return nullptr;
}
// 第三種情況：其左孩子為空，右孩子不為空，刪除節(jié)點(diǎn)，右孩子補(bǔ)位 ，返回右孩子為根節(jié)點(diǎn)
else if (root->left == nullptr) {
auto retNode = root->right;
///! 內(nèi)存釋放
delete root;
return retNode;
}
// 第四種情況：其右孩子為空，左孩子不為空，刪除節(jié)點(diǎn)，左孩子補(bǔ)位，返回左孩子為根節(jié)點(diǎn)
else if (root->right == nullptr) {
auto retNode = root->left;
///! 內(nèi)存釋放
delete root;
return retNode;
}
// 第五種情況：左右孩子節(jié)點(diǎn)都不為空，則將刪除節(jié)點(diǎn)的左子樹放到刪除節(jié)點(diǎn)的右子樹的最左面節(jié)點(diǎn)的左孩子的位置
// 并返回刪除節(jié)點(diǎn)右孩子為新的根節(jié)點(diǎn)。
else {
TreeNode* cur = root->right; // 找右子樹最左面的節(jié)點(diǎn)
while(cur->left != nullptr) {
cur = cur->left;
}
cur->left = root->left; // 把要?jiǎng)h除的節(jié)點(diǎn)（root）左子樹放在cur的左孩子的位置
TreeNode* tmp = root; // 把root節(jié)點(diǎn)保存一下，下面來刪除
root = root->right; // 返回舊root的右孩子作為新root
delete tmp; // 釋放節(jié)點(diǎn)內(nèi)存（這里不寫也可以，但C++最好手動(dòng)釋放一下吧）
return root;
}
}
if (root->val > key) root->left = deleteNode(root->left, key);
if (root->val < key) root->right = deleteNode(root->right, key);
return root;
}
};
到了這里，關(guān)于代碼隨想錄二刷day22 |二叉樹之 235. 二叉搜索樹的最近公共祖先 701.二叉搜索樹中的插入操作 450.刪除二叉搜索樹中的節(jié)點(diǎn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
