二叉搜索樹（BST）是二叉樹的一種特殊表示形式，它滿足如下特性：
每個節點中的值必須大于（或等于）存盤在其左側子樹中的任何值，
每個節點中的值必須小于（或等于）存盤在其右子樹中的任何值，
1.Leetcode98. 驗證二叉搜索樹
法一：利用二叉樹的性質，根結點的值大于左子樹上的點，小于右子樹上的點
const long long MAX=2e31;
const long long MIN=-MAX;
class Solution {
public:
bool isValidBST(TreeNode* root) {
bool ans=search(root,MIN,MAX);
return ans;
}
bool search(TreeNode *root,long long l,long long r){
if(root==NULL)return true;
if(root->val<=l||root->val>=r){
return false;
}
return search(root->left,l,root->val)&&search(root->right,root->val,r);
}
};
法二：二叉搜索樹中序遍歷的結果一定是單調遞增的
class Solution {
public:
bool isValidBST(TreeNode* root) {
stack<TreeNode*>st;
TreeNode *cur=root;
long long num=-2*1e10;
while(cur||!st.empty()){
while(cur){
st.push(cur);
cur=cur->left;
}
cur=st.top();
st.pop();
if(num>=cur->val){
return false;
}
num=cur->val;
cur=cur->right;
}
return true;
}
};
2.Leetcode173. 二叉搜索樹迭代器
class BSTIterator {
public:
TreeNode *cur;
stack<TreeNode*>st;
BSTIterator(TreeNode* root) {
cur=root;
}
int next() {
while(cur){
st.push(cur);
cur=cur->left;
}
cur=st.top();
st.pop();
int ans=cur->val;
cur=cur->right;
return ans;
}
bool hasNext() {
return cur||!st.empty();
}
};
3.Leetcode700. 二叉搜索樹中的搜索
class Solution {
public:
TreeNode *ans=NULL;
TreeNode* searchBST(TreeNode* root, int val) {
if(root==NULL)return root;
if(root->val==val)return root;
if(root->val>val)ans=searchBST(root->left,val);
if(root->val<val)ans=searchBST(root->right,val);
return ans;
}
};
4.Leetcode701. 二叉搜索樹中的插入操作
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==NULL){
root=new TreeNode(val);
return root;
}
if(root->val>val)root->left=insertIntoBST(root->left,val);
if(root->val<val)root->right=insertIntoBST(root->right,val);
return root;
}
};
5.Leetcode450. 洗掉二叉搜索樹中的節點
有許多不同的洗掉節點的方法,為了使整體操作變化最小，用一個合適的子節點來替換要洗掉的目標節點，根據其子節點的個數，我們需考慮以下三種情況：
- 如果目標節點沒有子節點，我們可以直接移除該目標節點，
- 如果目標節只有一個子節點，我們可以用其子節點作為替換，
- 如果目標節點有兩個子節點，我們需要用其中序 后繼節點或者前驅節點來替換，再洗掉該目標節點，
要洗掉的節點不是葉子節點且擁有右節點，則該節點可以由該節點的后繼節點進行替代，該后繼節點位于右子樹中較低的位置，然后可以從后繼節點的位置遞回向下操作以洗掉后繼節點，
要洗掉的節點不是葉子節點，且沒有右節點但是有左節點，這意味著它的后繼節點在它的上面，但是我們并不想回傳，我們可以使用它的前驅節點進行替代，然后再遞回的向下洗掉前驅節點，
Successor 代表的是中序遍歷序列的下一個節點，即比當前節點大的最小節點，簡稱后繼節點， 先取當前節點的右節點，然后一直取該節點的左節點，直到左節點為空，則最后指向的節點為后繼節點，
TreeNode * successor(TreeNode *root){
root=root->right;
while(root->left){
root=root->left;
}
return root;
}
Predecessor 代表的是中序遍歷序列的前一個節點，即比當前節點小的最大節點，簡稱前驅節點，先取當前節點的左節點，然后取該節點的右節點，直到右節點為空，則最后指向的節點為前驅節點，
TreeNode *predecessor(TreeNode *root){
root=root->left;
while(root->right){
root=root->right;
}
return root;
}
class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key){
if(root==NULL)return NULL;
if(root->val==key){
if(!root->left&&!root->right){
return NULL;
}else if(root->right){
TreeNode *node=new TreeNode(successor(root)->val);
node->left=root->left;
node->right=root->right;
node->right=deleteNode(node->right,node->val);
return node;
}else if(!root->right&&root->left){
TreeNode *node=new TreeNode(precessor(root)->val);
node->left=root->left;
node->right=root->right;
node->left=deleteNode(node->left,node->val);
return node;
}
}
TreeNode *l=deleteNode(root->left,key);
TreeNode *r=deleteNode(root->right,key);
root->left=l;
root->right=r;
return root;
}
TreeNode *successor(TreeNode *root){
root=root->right;
while(root->left){
root=root->left;
}
return root;
}
TreeNode *precessor(TreeNode*root){
root=root->left;
while(root->right){
root=root->right;
}
return root;
}
};
二叉搜索樹的有優點是，即便在最壞的情況下，也允許你在O(h)的時間復雜度內執行所有的搜索、插入、洗掉操作，
6.Leetcode235. 二叉搜索樹的最近公共祖先
法一：自底向上遞回，適用于一般二叉樹
class Solution {
public:
TreeNode *ans;
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)return NULL;
search(root,p,q);
return ans;
}
bool search(TreeNode *root,TreeNode*p,TreeNode *q){
if(root==NULL)return false;
bool pr=search(root->left,p,q);
bool qr=search(root->right,p,q);
if(pr&&qr||(root==p||root==q)&&(pr||qr)){
ans=root;
return true;
}
return root==q||root==p||qr||pr;
}
};
法二：
利用二叉搜索樹的性質，我們可以快速地找出樹中的某個節點以及從根節點到該節點的路徑
如果當前節點的值大于 p 和 q 的值，說明 p 和 q 應該在當前節點的左子樹，因此將當前節點移動到它的左子節點；
如果當前節點的值小于 p 和 q 的值，說明 p 和 q 應該在當前節點的右子樹，因此將當前節點移動到它的右子節點；
如果當前節點的值不滿足上述兩條要求，那么說明當前節點就是分岔點，此時，p 和 q 要么在當前節點的不同的子樹中，要么其中一個就是當前節點，
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root==NULL)return NULL;
TreeNode *ans=root;
while(ans){
if(ans->val>p->val&&ans->val>q->val){
ans=ans->left;
}else if(ans->val<p->val&&ans->val<q->val){
ans=ans->right;
}else{
break;
}
}
return ans;
}
};
高度平衡的二叉搜索樹
一個高度平衡的二叉搜索樹（平衡二叉搜索樹）是在插入和洗掉任何節點之后，可以自動保持其高度最小，也就是說，有 N 個節點的平衡二叉搜索樹，它的高度是 logN ，并且，每個節點的兩個子樹的高度不會相差超過 1，
二叉樹及其相關操作, 包括搜索、插入、洗掉，當分析這些操作的時間復雜度時，我們需要注意的是樹的高度是十分重要的考量因素，以搜索操作為例，如果二叉搜索樹的高度為 h ，則時間復雜度為 O(h) ，二叉搜索樹的高度的確很重要，
所以，我們來討論一下樹的節點總數 N 和高度 h 之間的關系，對于一個平衡二叉搜索樹, 我們已經在前文中提過，
但一個普通的二叉搜索樹，在最壞的情況下，它可以退化成一個鏈，
因此，具有 N 個節點的二叉搜索樹的高度在 logN 到 N 區間變化，也就是說，搜索操作的時間復雜度可以從 logN 變化到 N ，這是一個巨大的性能差異，
所以說，高度平衡的二叉搜索樹對提高性能起著重要作用，
高度平衡的二叉搜索樹在實際中被廣泛使用，因為它可以在 O(logN) 時間復雜度內執行所有搜索、插入和洗掉操作，
常見的的高度平衡二叉樹：
紅黑樹
AVL樹
伸展樹
樹堆
平衡二叉搜索樹的概念經常運用在 Set 和 Map 中，Set 和 Map 的原理相似，
通常，有兩種最廣泛使用的集合**：散列集合（Hash Set）和 樹集合（Tree Set）**，
樹集合，Java 中的 Treeset 或者 C++ 中的 set ，是由高度平衡的二叉搜索樹實作的，因此，搜索、插入和洗掉的時間復雜度都是 O(logN) ，
散列集合，Java 中的 HashSet 或者 C++ 中的 unordered_set ，是由哈希實作的，但是平衡二叉搜索樹也起到了至關重要的作用，當存在具有相同哈希鍵的元素過多時，將花費 O(N) 時間復雜度來查找特定元素，其中N是具有相同哈希鍵的元素的數量， 通常情況下，使用高度平衡的二叉搜索樹將把時間復雜度從 O(N) 改善到 O(logN) ，
哈希集和樹集之間的本質區別在于樹集中的鍵是有序的，
7.110. 平衡二叉樹
class Solution {
public:
bool ans=true;
bool isBalanced(TreeNode* root) {
if(root==NULL)return ans;
search(root);
return ans;
}
int search(TreeNode *root){
if(root==NULL)return 0;
int l=search(root->left);
int r=search(root->right);
if(abs(l-r)>1){
ans=false;
return -1;
}
return l>r?l+1:r+1;
}
};
8.Leetcode108. 將有序陣列轉換為二叉搜索樹
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return helper(nums, 0, nums.size() - 1);
}
TreeNode* helper(vector<int>& nums, int left, int right) {
if (left > right) {
return nullptr;
}
// 總是選擇中間位置左邊的數字作為根節點
int mid = (left + right) / 2;
TreeNode* root = new TreeNode(nums[mid]);
root->left = helper(nums, left, mid - 1);
root->right = helper(nums, mid + 1, right);
return root;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/357047.html
標籤：其他