二叉搜索樹（BST）是二叉樹的一種特殊表示形式，它滿足如下特性：

每個(gè)節(jié)點(diǎn)中的值必須大于（或等于）存儲(chǔ)在其左側(cè)子樹中的任何值。
每個(gè)節(jié)點(diǎn)中的值必須小于（或等于）存儲(chǔ)在其右子樹中的任何值。

1.Leetcode98. 驗(yàn)證二叉搜索樹

法一：利用二叉樹的性質(zhì)，根結(jié)點(diǎn)的值大于左子樹上的點(diǎn)，小于右子樹上的點(diǎn)

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);            }};

法二：二叉搜索樹中序遍歷的結(jié)果一定是單調(diào)遞增的

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. 刪除二叉搜索樹中的節(jié)點(diǎn)

有許多不同的刪除節(jié)點(diǎn)的方法,為了使整體操作變化最小，用一個(gè)合適的子節(jié)點(diǎn)來替換要?jiǎng)h除的目標(biāo)節(jié)點(diǎn)。根據(jù)其子節(jié)點(diǎn)的個(gè)數(shù)，我們需考慮以下三種情況：

1. 如果目標(biāo)節(jié)點(diǎn)沒有子節(jié)點(diǎn)，我們可以直接移除該目標(biāo)節(jié)點(diǎn)。
2. 如果目標(biāo)節(jié)只有一個(gè)子節(jié)點(diǎn)，我們可以用其子節(jié)點(diǎn)作為替換。
3. 如果目標(biāo)節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，我們需要用其中序 后繼節(jié)點(diǎn)或者前驅(qū)節(jié)點(diǎn)來替換，再刪除該目標(biāo)節(jié)點(diǎn)。
   要?jiǎng)h除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)且擁有右節(jié)點(diǎn)，則該節(jié)點(diǎn)可以由該節(jié)點(diǎn)的后繼節(jié)點(diǎn)進(jìn)行替代，該后繼節(jié)點(diǎn)位于右子樹中較低的位置。然后可以從后繼節(jié)點(diǎn)的位置遞歸向下操作以刪除后繼節(jié)點(diǎn)。
   要?jiǎng)h除的節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，且沒有右節(jié)點(diǎn)但是有左節(jié)點(diǎn)。這意味著它的后繼節(jié)點(diǎn)在它的上面，但是我們并不想返回。我們可以使用它的前驅(qū)節(jié)點(diǎn)進(jìn)行替代，然后再遞歸的向下刪除前驅(qū)節(jié)點(diǎn)。

Successor 代表的是中序遍歷序列的下一個(gè)節(jié)點(diǎn)。即比當(dāng)前節(jié)點(diǎn)大的最小節(jié)點(diǎn)，簡(jiǎn)稱后繼節(jié)點(diǎn)。 先取當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)，然后一直取該節(jié)點(diǎn)的左節(jié)點(diǎn)，直到左節(jié)點(diǎn)為空，則最后指向的節(jié)點(diǎn)為后繼節(jié)點(diǎn)。

TreeNode * successor(TreeNode *root){     root=root->right;     while(root->left){        root=root->left;     }     return root;}

Predecessor 代表的是中序遍歷序列的前一個(gè)節(jié)點(diǎn)。即比當(dāng)前節(jié)點(diǎn)小的最大節(jié)點(diǎn)，簡(jiǎn)稱前驅(qū)節(jié)點(diǎn)。先取當(dāng)前節(jié)點(diǎn)的左節(jié)點(diǎn)，然后取該節(jié)點(diǎn)的右節(jié)點(diǎn)，直到右節(jié)點(diǎn)為空，則最后指向的節(jié)點(diǎn)為前驅(qū)節(jié)點(diǎn)。

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;    }};

二叉搜索樹的有優(yōu)點(diǎn)是，即便在最壞的情況下，也允許你在O(h)的時(shí)間復(fù)雜度內(nèi)執(zhí)行所有的搜索、插入、刪除操作。

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;    }};

法二：
利用二叉搜索樹的性質(zhì)，我們可以快速地找出樹中的某個(gè)節(jié)點(diǎn)以及從根節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑
如果當(dāng)前節(jié)點(diǎn)的值大于 p 和 q 的值，說明 p 和 q 應(yīng)該在當(dāng)前節(jié)點(diǎn)的左子樹，因此將當(dāng)前節(jié)點(diǎn)移動(dòng)到它的左子節(jié)點(diǎn)；

如果當(dāng)前節(jié)點(diǎn)的值小于 p 和 q 的值，說明 p 和 q 應(yīng)該在當(dāng)前節(jié)點(diǎn)的右子樹，因此將當(dāng)前節(jié)點(diǎn)移動(dòng)到它的右子節(jié)點(diǎn)；

如果當(dāng)前節(jié)點(diǎn)的值不滿足上述兩條要求，那么說明當(dāng)前節(jié)點(diǎn)就是分岔點(diǎn)。此時(shí)，p 和 q 要么在當(dāng)前節(jié)點(diǎn)的不同的子樹中，要么其中一個(gè)就是當(dāng)前節(jié)點(diǎn)。

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;    }    };

高度平衡的二叉搜索樹
一個(gè)高度平衡的二叉搜索樹（平衡二叉搜索樹）是在插入和刪除任何節(jié)點(diǎn)之后，可以自動(dòng)保持其高度最小。也就是說，有 N 個(gè)節(jié)點(diǎn)的平衡二叉搜索樹，它的高度是 logN 。并且，每個(gè)節(jié)點(diǎn)的兩個(gè)子樹的高度不會(huì)相差超過 1。
二叉樹及其相關(guān)操作, 包括搜索、插入、刪除。當(dāng)分析這些操作的時(shí)間復(fù)雜度時(shí)，我們需要注意的是樹的高度是十分重要的考量因素。以搜索操作為例，如果二叉搜索樹的高度為 h ，則時(shí)間復(fù)雜度為 O(h) 。二叉搜索樹的高度的確很重要。
所以，我們來討論一下樹的節(jié)點(diǎn)總數(shù) N 和高度 h 之間的關(guān)系。對(duì)于一個(gè)平衡二叉搜索樹, 我們已經(jīng)在前文中提過，

但一個(gè)普通的二叉搜索樹，在最壞的情況下，它可以退化成一個(gè)鏈。

因此，具有 N 個(gè)節(jié)點(diǎn)的二叉搜索樹的高度在 logN 到 N 區(qū)間變化。也就是說，搜索操作的時(shí)間復(fù)雜度可以從 logN 變化到 N 。這是一個(gè)巨大的性能差異。
所以說，高度平衡的二叉搜索樹對(duì)提高性能起著重要作用。

高度平衡的二叉搜索樹在實(shí)際中被廣泛使用，因?yàn)樗梢栽?O(logN) 時(shí)間復(fù)雜度內(nèi)執(zhí)行所有搜索、插入和刪除操作。
常見的的高度平衡二叉樹：
紅黑樹
AVL樹
伸展樹
樹堆
平衡二叉搜索樹的概念經(jīng)常運(yùn)用在 Set 和 Map 中。Set 和 Map 的原理相似。
通常，有兩種最廣泛使用的集合**：散列集合（Hash Set）和 樹集合（Tree Set）**。

樹集合，Java 中的 Treeset 或者 C++ 中的 set ，是由高度平衡的二叉搜索樹實(shí)現(xiàn)的。因此，搜索、插入和刪除的時(shí)間復(fù)雜度都是 O(logN) 。

散列集合，Java 中的 HashSet 或者 C++ 中的 unordered_set ，是由哈希實(shí)現(xiàn)的，但是平衡二叉搜索樹也起到了至關(guān)重要的作用。當(dāng)存在具有相同哈希鍵的元素過多時(shí)，將花費(fèi) O(N) 時(shí)間復(fù)雜度來查找特定元素，其中N是具有相同哈希鍵的元素的數(shù)量。 通常情況下，使用高度平衡的二叉搜索樹將把時(shí)間復(fù)雜度從 O(N) 改善到 O(logN) 。

哈希集和樹集之間的本質(zhì)區(qū)別在于樹集中的鍵是有序的。

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. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹

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;        }        // 總是選擇中間位置左邊的數(shù)字作為根節(jié)點(diǎn)        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;    }};