代碼隨想錄算法訓練營第60期第二十天打卡

? ? ? ? 大家好，今天我們繼續進入二叉樹的章節，二叉樹章節應該已經過半了，大家再堅持一下，那么廢話不多說，我們繼續今天的內容。

第一題對應力扣編號為235的二叉搜索樹的最近公共祖先

? ? ? ? 其實我們上次任務就接觸過了二叉樹的最近公共祖先，其實很難，我們很容易就迷糊我們究竟如何返回以及什么情況下才會有最近公共祖先，其實最近的公共祖先就是兩個節點分別處在最近的左右子樹中，兩邊均返回true這種情況下我們就找到了最近公共祖先，那我們知道二叉搜索樹是一種特殊的二叉樹，那么它的最近公共祖先應該如何找呢？我們一起走進我們今天的第一題：

? ? ? 其實這跟我們上次的二叉樹的最近公共祖先是一樣的要求，我們原來的思路是自底向上回溯，遇到一個節點的左子樹里有p，右子樹里有q，那么當前節點就是最近公共祖先。很明顯我們應該好好利用二叉搜索樹的特點來助力我們解決這道題目，因為是有序樹，所以如果中間節點是 q 和 p 的公共祖先，那么中節點的數組一定是在 [p, q]區間的。即中節點 > p && 中節點 < q 或者中節點 > q && 中節點 < p。我們可以利用這個二叉搜索樹的性質，但是我們會思考我們這樣找到的節點究竟是不是最近的公共祖先，我給出大家一個代碼隨想錄上的例子：

? ? ? ?其實我們可以看到p,q的最近公共祖先是5，通過圖我們可以看到如何我們從5向左遍歷我們將會失去成為p的祖先的可能，同理如果我們向右遍歷我們將會失去成為q的祖先的可能，所以當我們從上向下去遞歸遍歷，第一次遇到 cur節點是數值在[q, p]區間中，那么cur就是 q和p的最近公共祖先。因此我們可以得到如果我們從上往下遍歷如果我們第一次遇到 cur節點是數值在[q, p]區間中，那么cur就是 q和p的最近公共祖先。那我們就嘗試寫一下遞歸代碼，首先大家要明白單層遞歸的邏輯，如果我當前節點的值比p,q兩個節點的值都要小的話說明我們要尋找的目標應該是右邊，我們應該向右遍歷，相反如果我當前節點的值比p,q兩個節點的值都要大的話說明我們要尋找的目標應該是左邊，我們應該向左遍歷，因此這個二叉搜索樹由于有順序我們從上往下遞歸也是可以實現的，我們嘗試寫一下代碼：

class Solution {
private:TreeNode* traversal(TreeNode *cur, TreeNode* p, TreeNode *q){if (cur == NULL) return NULL;//這時候我們的搜索目標應該是在左邊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;//如果一邊大一邊小就說明這就是最近公共祖先了}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root, p, q);}
};

? ? ? ?這個代碼只要大家理解了我上面的思路就不難了，還是二叉搜索樹的特殊性質很重要。我們這道題就講解到這里，接下來我們進入下一道題目。

第二題對應力扣編號為701的題目二叉搜索樹中的插入操作

? ? ? ?我們來到了今天的第二題，這個是關于二叉搜索樹的插入操作，我們直接看到題目的具體要求：

? ? ? ? 要解決這道題目我感覺我們要明白的是我們應該考慮往左邊插還是往右邊插，這個其實我們還是得考慮二叉搜索樹的性質，那我們應該如何考慮呢？其實題目不算難，我們返回有效的結果就可以，也就是我們找到適合的插入位置并且這個地方是空節點我們就可以插入，那其實我們還是遞歸的過程，首先有一種特殊的情況如果我們的根節點是空節點我們就直接把題目中給出的節點插入到空節點就可以了，大家一起來看一看我們的遞歸代碼：

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);}else if (root -> val < val){root -> right = insertIntoBST(root -> right, val);}else return root;return root;}
};

? ? ? ? 我們還是搞明白我們插入的邏輯，首先就是空節點的話我們就直接插入到空節點就可以，如果我給出的值比根節點小，就說明我當前的值應該往左邊插入，如果我給出的值比根節點大，就說明我當前的值應該往右邊插入，如果相等我也無需插入了直接返回根節點了，根節點就可以取代我這個節點，這樣這個題目我們就解決了，相信大家可以明白，這道題難度不大，我們要進入下一道題目了。

第三題對應力扣編號為450的題目刪除二叉樹中的節點

? ? ? ?其實這跟上一道題目不就是異曲同工嗎？上一題我們需要插入，這一題我們刪除，我們就直接進入這道題目：

? ? ? ? ?首先還是我們得找到這個節點否則我們刪什么呢？還是遞歸對吧，我們要找到要刪除的節點，這里有一個地方很難，就是我調整二叉樹的時候不好理解，我要分的幾種情況我都在代碼注釋里給大家寫清楚了：

class Solution {
public:TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return root; // 第一種情況：沒找到刪除的節點，遍歷到空節點直接返回了if (root->val == key) {// 第二種情況：左右孩子都為空（葉子節點），直接刪除節點， 返回NULL為根節點if (root->left == nullptr && root->right == nullptr) {///! 內存釋放delete root;return nullptr;}// 第三種情況：其左孩子為空，右孩子不為空，刪除節點，右孩子補位 ，返回右孩子為根節點else if (root->left == nullptr) {auto retNode = root->right;///! 內存釋放delete root;return retNode;}// 第四種情況：其右孩子為空，左孩子不為空，刪除節點，左孩子補位，返回左孩子為根節點else if (root->right == nullptr) {auto retNode = root->left;///! 內存釋放delete root;return retNode;}// 第五種情況：左右孩子節點都不為空，則將刪除節點的左子樹放到刪除節點的右子樹的最左面節點的左孩子的位置// 并返回刪除節點右孩子為新的根節點。else {TreeNode* cur = root->right; // 找右子樹最左面的節點while(cur->left != nullptr) {cur = cur->left;}cur->left = root->left; // 把要刪除的節點（root）左子樹放在cur的左孩子的位置TreeNode* tmp = root;   // 把root節點保存一下，下面來刪除root = root->right;     // 返回舊root的右孩子作為新rootdelete tmp;             // 釋放節點內存（這里不寫也可以，但C++最好手動釋放一下吧）return root;}}if (root->val > key) root->left = deleteNode(root->left, key);if (root->val < key) root->right = deleteNode(root->right, key);return root;}
};

? ? ? 我重點講解最后的else的情況，就是左右子樹都不為空的時候我們刪除了節點我們應該如何調整這棵搜索二叉樹，這個相當難，我們舉個例子來理解一下：

? ? ? ?比方說這棵二叉樹，我們要刪除7這個節點的話我們不得不讓其左孩子或者右孩子繼位，但是我們知道二叉搜索樹的話節點7它的左子樹的值都是小于7的，右子樹的值都是大于7的，我們讓7的右孩子繼位，如果7沒了我們的左子樹就要去尋找新的父節點，我們選擇的是比7大一點的節點就是了，因此這個位置我們就找到了右子樹的最左邊的位置，這樣才可以保證我們將7刪除之后我所組成的二叉樹還是一棵二叉搜索樹，這就是本道題目最難想的地方，那我們也看一下它的代碼實現，代碼里前面的幾種情況都是很簡單的，上面代碼的注釋我也清晰標注了，關鍵看這種情況，首先拿到右孩子，讓右孩子繼承父節點的位置，接下來我們要安頓好原先父節點的左子樹，我們選擇的是右子樹的最左邊的位置，我們借助一個變量來保存父節點，然后我們將右孩子賦值給根節點，最后返回根節點就可以了，最后大家還要注意遞歸，什么情況下往左遞歸，什么情況下往右遞歸，這道題我就先給大家解釋道這里。