二叉搜索樹的最近公共祖先

不考慮二叉搜索樹這一條件的話，普通的二叉搜索樹搜索最近的公共祖先就是昨日的做法，這種做法也能解決二叉搜索樹的最近公共祖先。

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 如果當前節點為空，或者等于p或q，直接返回當前節點if (root == nullptr || root == p || root == q) {return root;}// 在左右子樹中遞歸尋找p和qTreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);// 如果左右子樹的返回值都不為空，說明當前節點就是最近公共祖先if (left != nullptr && right != nullptr) {return root;}// 否則，返回非空的子樹返回值return left != nullptr ? left : right;}
};

沒有用上二叉搜索樹這一條件，但也能解題，但效率較低。

針對二叉搜索樹，我們之前有做過，當對二叉搜索樹進行中序編歷時，結果是一個遞增的數組。即公共祖先，val值必定處于p和q之間。

當從根節點向下遍歷的過程中，如果遇到節點val值位于p和q之間，那么就尋找到了最近的公共祖先。具體參考代碼隨想錄B站視頻。

二叉搜索樹找祖先就有點不一樣了！| 235. 二叉搜索樹的最近公共祖先_嗶哩嗶哩_bilibilihttps://www.bilibili.com/video/BV1Zt4y1F7ww/?spm_id_from=333.788&vd_source=fc4a6e70e3a87b7ea67c2024e326e7c5從上到下遍歷，考慮層序遍歷的方式，具體代碼如下：

class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {queue<TreeNode*>queue;if(root == nullptr){return nullptr;}queue.push(root);TreeNode*cur = root;int min = p->val>q->val?q->val:p->val;//找到p，q中val的較小值int max = p->val<q->val?q->val:p->val;//找到p,q中val的較大值while(!queue.empty()){//層序遍歷過程int level_size = queue.size();for(int i = 0; i <level_size; i ++){cur = queue.front();queue.pop();if(cur->val<=max and cur->val>=min){return cur;}//找到節點屬于p,q間則返回if(cur->left)queue.push(cur->left);if(cur->right)queue.push(cur->right);} }return nullptr;}
};

算法的時間復雜度和空間復雜度均為O(n)。

前序遞歸，中左右，參考代碼隨想錄

代碼隨想錄 (programmercarl.com)https://programmercarl.com/0235.%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E7%9A%84%E6%9C%80%E8%BF%91%E5%85%AC%E5%85%B1%E7%A5%96%E5%85%88.html#%E6%80%9D%E8%B7%AF

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;}
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {return traversal(root, p, q);}
};

二叉搜索樹中的插入操作

由于樹中的節點值是獨一無二的，在二叉搜索樹中尋找值應插入的節點的父節點位置，然后創建一個新節點并將其插入即可。

代碼整體如下

class Solution {
public:// 在二叉搜索樹中查找適合插入新節點的位置，并返回該位置的父節點TreeNode* findBST(TreeNode* root, int val) {// 如果當前節點為空，返回nullptr，表示沒有找到合適的插入位置if (root == nullptr) return nullptr;// 如果val小于當前節點的值，應該在左子樹中繼續查找if (val < root->val) {// 如果左子節點為空，當前位置就是適合插入新節點的位置if (root->left == nullptr) return root;// 否則，在左子樹中繼續查找return findBST(root->left, val);} else {// 如果val大于或等于當前節點的值，應該在右子樹中繼續查找// 如果右子節點為空，當前位置就是適合插入新節點的位置if (root->right == nullptr) return root;// 否則，在右子樹中繼續查找return findBST(root->right, val);}}// 在二叉搜索樹中插入一個新的節點TreeNode* insertIntoBST(TreeNode* root, int val) {// 創建新節點TreeNode* newnode = new TreeNode(val);// 如果樹為空，新節點即為根節點if (root == nullptr) {return newnode;}// 查找適合插入新節點的位置，并得到該位置的父節點TreeNode* parent = findBST(root, val);// 根據val的值決定新節點是作為左子節點還是右子節點if (val < parent->val) {parent->left = newnode;} else {parent->right = newnode;}// 返回根節點return root;}
};

算法的時間復雜度為O(logn)（二叉搜索樹，最差為O(n)），空間復雜度為O(1)。

刪除二叉搜索樹中的節點

有五種情況

1.未找到需要刪除的節點

2.刪除的是葉節點

3.刪除的節點僅有右子樹

4.刪除的節點僅有左子樹

5.刪除的節點左右子樹都在

針對這五種情況，有以下五種解答方案

1.直接返回二叉搜索樹的根節點

2.直接刪除即可

3.將右孩子代替被刪除的節點

4.將左孩子代替被刪除的節點

5.有兩種解決方式，分別是讓被刪除節點的右孩子或左孩子即位，以右孩子即位，查找右子樹下的最小值節點，將節點的左子樹全部接入該節點，或以左孩子即位，查找左子樹下的最大值節點，將節點的右子樹全部接入該節點。

class Solution {
public:TreeNode* find_parent(TreeNode* root, int key) {if (root == nullptr || (root->left == nullptr && root->right == nullptr)) {return nullptr; // 如果當前節點為空或為葉節點，返回nullptr}if (root->left != nullptr && root->left->val == key) {return root; // 如果左子節點的值等于key，返回當前節點作為父節點}if (root->right != nullptr && root->right->val == key) {return root; // 如果右子節點的值等于key，返回當前節點作為父節點}if (key < root->val) {return find_parent(root->left, key); // 如果key小于當前節點的值，遞歸地在左子樹中查找} else {return find_parent(root->right, key); // 如果key大于或等于當前節點的值，遞歸地在右子樹中查找}}TreeNode* deleteNode(TreeNode* root, int key) {if (root == nullptr) return nullptr;if (root->val == key) {// 要刪除的節點是根節點if (root->left == nullptr) return root->right; // 只有右子樹if (root->right == nullptr) return root->left; // 只有左子樹// 有兩個子節點，找到右子樹的最小節點TreeNode* minNode = getMin(root->right);root->val = minNode->val; // 將右子樹的最小節點的值賦給當前節點root->right = deleteNode(root->right, minNode->val); // 刪除右子樹中的最小節點} else if (key < root->val) {root->left = deleteNode(root->left, key); // 在左子樹中遞歸刪除} else {root->right = deleteNode(root->right, key); // 在右子樹中遞歸刪除}return root;}TreeNode* getMin(TreeNode* node) {while (node->left != nullptr) node = node->left;return node;}
};

算法的時間復雜度需要考慮樹的高度，查找樹中要刪除的節點，需要O(logn)的時間，當需要刪除的節點有兩個子節點時，需要找到右子樹中的最小節點，這同樣需要O(logn)的時間，最壞情況下時間復雜度為O(logn)。

空間復雜度主要取決于遞歸棧的深度，因此，空間復雜度也為O(logn)。