# Leetcode刷題學習筆記 -- Binary Search Tree(BST)
## 簡介
ref : [wiki](https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9)
二元搜尋樹（英語：Binary Search Tree），也稱為有序二元樹（ordered binary tree）或排序二元樹（sorted binary tree），是指一棵空樹或者具有下列性質的二元樹：
1. 若任意節點的左子樹不空，則左子樹上所有節點的值均小於它的根節點的值；
2. 若任意節點的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
3. 任意節點的左、右子樹也分別為二元搜尋樹；
如果BST，呈現不平衡的狀態，例如都串在同一個直線。那最差情況都是O(n)。
| 演算法 | 平均 | 最差 |
| -------- | -------- | -------- |
| 空間 | O(n) | O(n) |
| 搜尋 | O(logn) | O(n) |
| 插入 | O(logn) | O(n) |
| 刪除 | O(logn) | O(n) |
二元搜尋樹的最壞效率是O(n)，但它支援動態查詢，且有很多改進版的二元搜尋樹可以使樹高為O(log n)，從而將最壞效率降至O(log n)，如==AVL樹==、==紅黑樹==等。
## Inorder Traversal
當BST(Binary Search Tree)使用Inorder Traversal的時候，可以得到遞增或是遞減的數列。
以下的程式碼是得到遞增序列。
```cpp
void dfs(TreeNode *root, vector<int>& rtn) {
if(!root) return;
dfs(root->left);
rtn.push_back(root->val);
dfs(root->right);
}
```
以下的程式碼可以得到遞減序列。
```cpp
void dfs(TreeNode *root, vector<int>& rtn) {
if(!root) return;
dfs(root->right);
rtn.push_back(root->val);
dfs(root->left);
}
```
另外也可以用stack來實現
```cpp
void inorder(TreeNode *root) {
stack<TreeNode *> st;
TreeNode *p = root;
while(p || !st.empty()) {
// 先把全部的left存起來
while(p) {
st.push(p);
p = p->left;
}
// 取出最後一個left node
p = st.top(); st.pop();
cout << p->val << endl;
// 檢查right child node
p = p->right;
}
}
```
很多題目會根據上訴兩種來變形。
1. 遞增訪問
+ [230. Kth Smallest Element in a BST](/neNmzsZsRrmYQ-RtPWbYxA?both#230-Kth-Smallest-Element-in-a-BST)
+ [897. Increasing Order Search Tree](/neNmzsZsRrmYQ-RtPWbYxA?both#897-Increasing-Order-Search-Tree)
+ [99. Recover Binary Search Tree]()
2. 遞減訪問
+ [538. Convert BST to Greater Tree](/neNmzsZsRrmYQ-RtPWbYxA?both#538-Convert-BST-to-Greater-Tree)
3. 找兩個node之間最小的差
+ [783. Minimum Distance Between BST Nodes](/neNmzsZsRrmYQ-RtPWbYxA?both#783-Minimum-Distance-Between-BST-Nodes)
### [99. Recover Binary Search Tree](https://leetcode.com/problems/recover-binary-search-tree/)
在BST中有兩個node被交換了，試復原成原本的BST。
> 1. 使用inorder traversal。如果是正常的BST會得到從小到大的排列。
> 2. 題目只有兩個node被交換了，例如
> 1, 2, 3, 4, 5, 6 --> 1, **5**, 3, 4, **2**, 6
> 5, 3 --> prev > curr, 取前者
> 4, 2 --> prev > cur, 取後者
```cpp
void recoverTree(TreeNode* root) {
TreeNode *prev = nullptr, *first = nullptr, *second = nullptr, *p = root;
stack<TreeNode *> st;
while(p || !st.empty()) {
while(p) {
st.push(p);
p = p->left;
}
p = st.top(); st.pop();
if(prev && prev->val > p->val) {
if(!first) first = prev; // 取前者
second = p; // 取後者
}
prev = p;
p = p->right;
}
swap(first->val, second->val);
}
```
### [230. Kth Smallest Element in a BST](https://leetcode.com/problems/kth-smallest-element-in-a-bst/)
找出BST中，第k個最小的值。
> 1. 在BST中使用Inorder Traversal來找出第k個數值。
```cpp
class Solution {
int k, rtn;
void helper(TreeNode *root) {
if(!root) return;
helper(root->left);
k--;
if(k == 0) rtn = root->val;
else if(k < 0) return;
helper(root->right);
}
public:
int kthSmallest(TreeNode* root, int k) {
this->k = k;
helper(root);
return rtn;
}
};
```
### [897. Increasing Order Search Tree](https://leetcode.com/problems/increasing-order-search-tree/)
把BST，從小到大，依序串在node的右邊。
> 1. 對BST做Inorder Traversal。
> 2. 對每個node，把left child設成nullptr, 把right child設成下一個走訪的node。
```cpp
class Solution {
void helper(TreeNode *root) {
if(!root) return;
helper(root->left);
root->left = nullptr;
cur->right = root;
cur = cur->right;
helper(root->right);
}
TreeNode *cur;
public:
TreeNode* increasingBST(TreeNode* root) {
TreeNode *newroot = new TreeNode();
cur = newroot;
helper(root);
return newroot->right;
}
};
```
### [538. Convert BST to Greater Tree](https://leetcode.com/problems/convert-bst-to-greater-tree/)
給你一個BST，試給出一個Greater Tree。
> 1. 對BST做Inorder Traversal(從大到小)。
> 2. 每遇到一個node就把數值相加，並更新到目前的node。
```cpp
class Solution {
int sum = 0;
void helper(TreeNode *root) {
if(!root) return;
helper(root->right);
sum += root->val;
root->val = sum;
helper(root->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
helper(root);
return root;
}
};
```
### [450. Delete Node in a BST(Medium)](https://leetcode.com/problems/delete-node-in-a-bst/)
給你一個key，刪除BST中和key值一樣的node，並且保持原本的樹還是BST。
例如:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
解題思路:
> case 1: 如果要刪除的node是leaf，那就直接刪除。
> case 2: 如果要刪除的node不是leaf，但是只有一個child，則直接把child接上來。
> case 3: ==如果要刪除的node不是leaf，而且有兩個child!==，為了保持刪除後依然是BST，所以勢必要調整樹的結構。如何做到最小調整? ==使用右子樹最小值，或是左子樹最大值代替原本欲刪除的node，就可以達到最小的修正。==
```cpp=
TreeNode* deleteNode(TreeNode* root, int key) {
if(!root) return nullptr;
if(key > root->val)
root->right = deleteNode(root->right, key);
else if(key < root->val)
root->left = deleteNode(root->left, key);
else {
// 只有一個child node，或是node為leaf
if(!root->left || !root->right)
root = root->left ? root->left : root->right;
else {
// node有兩個child
// 找出右子樹最小值
TreeNode *cur = root->right;
while(cur->left) cur = cur->left;
root->val = cur->val;
// 刪除右子樹最小值的node
root->right = deleteNode(root->right, cur->val);
}
}
return root;
}
```
找出左邊子樹的最大值一樣也可以。
```cpp=
// 找出左子樹最大值
TreeNode *cur = root->left;
while(cur->right) cur = cur->right;
root->val = cur->val;
// 刪除左子樹最大值的node
root->left = deleteNode(root->left, cur->val);
```
### [235. Lowest Common Ancestor of a Binary Search Tree(Easy)](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/)
給你兩個在BST中的node, p和q。找出這兩個的共同祖先(ancestor)。
> 1. 因為沒說明p, q是否有什麼關係，所以必須用max(), min()找出最大最小值。
> 2. root->val > max(p->val, q->val) 表示p和q都在root的左側。
> 3. root->val < min(p->val, q->val) 表示p和q都在root的右側。
> 4. 不是上述兩種狀況表示root即為共同的祖先。
```cpp=
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(!root) return nullptr;
else if(root->val > max(p->val, q->val))
return lowestCommonAncestor(root->left, p, q);
else if(root->val < min(p->val, q->val))
return lowestCommonAncestor(root->right, p, q);
else // root->val > min(p->val, q->val) && root->val < max(p->val, q->val)
return root;
}
```
### [783. Minimum Distance Between BST Nodes](https://leetcode.com/problems/minimum-distance-between-bst-nodes/description/)
在BST中，找出兩個node之間最小的差。
> 1. 因為BST使用inorder traversal可以得到遞增數列，使用此特性比較前後兩個node，就可以找出最小的差值。
```cpp=
class Solution {
// 在BST中使用inorder可以得到從小到大的排序。
int ans = 1e5 + 1, prev = -1;
void helper(TreeNode *root) {
if(!root) return;
helper(root->left);
if(prev != -1)
ans = min(ans, root->val - prev);
prev = root->val;
helper(root->right);
}
public:
int minDiffInBST(TreeNode* root) {
helper(root);
return ans;
}
};
```
###### tags: `leetcode` `刷題`
Sign in with Wallet
Connect another wallet