一、概念

二叉搜索樹（Binary Search Tree，簡稱 BST）是一種特殊的二叉樹，其核心特性圍繞 “節點值的有序性” 展開。

定義性特征：對于二叉搜索樹中的任意節點，滿足：

• 左子樹所有節點的值 < 當前節點的值；
• 右子樹所有節點的值 > 當前節點的值；
• 左、右子樹本身也必須是二叉搜索樹（遞歸滿足上述條件）。
• 標準 BST 中通常不允許存在值相等的節點。
  

衍生特征：

• 中序遍歷結果為升序序列，得到的節點值序列是嚴格遞增的。這是 BST 最常用的特性之一，可用于驗證一棵樹是否為 BST，或通過升序序列反向構造 BST。
• 樹中最小值一定是最左側的葉子節點（一路向左子樹遍歷，直到無左孩子）；
  樹中最大值一定是最右側的葉子節點（一路向右子樹遍歷，直到無右孩子）。
• 查找目標值target的過程類似二分查找：若當前節點值等于target，找到目標；若target小于當前節點值，遞歸查找左子樹；若target大于當前節點值，遞歸查找右子樹。時間復雜度為O(log n)，最壞情況（退化為鏈表）為O(n)。
• 平衡二叉樹是 BST 的進階，通過額外機制保證左右子樹高度差不超過 1，避免了 BST 在極端情況下退化為鏈表。

二、構造

序號	題目	鏈接
1	先序序列構造	https://leetcode.cn/problems/construct-binary-search-tree-from-preorder-traversal/description/?envType=problem-list-v2&envId=tree
2	中序序列構造	https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/?envType=problem-list-v2&envId=tree
3	中序有序鏈表構造	https://leetcode.cn/problems/convert-sorted-list-to-binary-search-tree/?envType=problem-list-v2&envId=tree
4	BST轉換為中序有序鏈表	https://leetcode.cn/problems/increasing-order-search-tree/description/?envType=problem-list-v2&envId=tree
5	BST的序列化和反序列化	https://leetcode.cn/problems/serialize-and-deserialize-bst/description/?envType=problem-list-v2&envId=tree
1	BST的種數1【總數】	https://leetcode.cn/problems/unique-binary-search-trees/description/?envType=problem-list-v2&envId=tree
2	BST的種數2【列舉】	https://leetcode.cn/problems/unique-binary-search-trees-ii/solutions/339143/bu-tong-de-er-cha-sou-suo-shu-ii-by-leetcode-solut/?envType=problem-list-v2&envId=tree

1.1先序序列 構造BST

先序序列的特點是：根左右。結合BST的特性可知：

• 序列的第一個元素一定是根節點
• 根【左（比根小）】【右（比根大）】。根節點后面的元素，只要比第一個元素小的都是BST的左子樹，右子樹同理。
  

TreeNode* build(vector<int>& pre,int start,int end){//遞歸的出口if (start > end) return nullptr;//根節點int rootVal=pre[start];TreeNode* root=new TreeNode(rootVal);// 找到左子樹與右子樹的分割點（第一個大于根節點值的位置為右子樹的第一個元素）int index;for(index=start+1;index<=end;index++){if(pre[index]>rootVal) break;}//遞歸構造左子樹和右子樹root->left = build(pre, start + 1, index - 1);root->right = build(pre, index, end);return root;
}

1.2中序序列 轉換為BST

與先序序列轉換一樣。中序序列的特點是：左根右。結合BST的性質。

• 序列的中間元素為樹的根節點。
• 【左】根【右】。在根節點左邊的為左子樹，根節點右邊的為右子樹（遞歸構造）

TreeNode* build(vector<int>& nums,int start,int end){if(start>end) return nullptr;int mid=(start+end)/2;int rootVal=nums[mid];TreeNode* root=new TreeNode(rootVal);root->left=build(nums,start,mid-1);root->right=build(nums,mid+1,end);return root;
}

1.3中序序列鏈表轉換為BST

有序鏈表轉換成二叉搜索樹的原理同 中序遍歷轉換為二叉樹。

TreeNode* build(ListNode* head,int left,int right){if(left>right) return nullptr;int mid=(left+right)/2;//訪問鏈表在mid處的值 p指向的是根節點ListNode* p=head;for(int i=1;i<=mid;i++){p=p->next;}TreeNode* root=new TreeNode(p->val);//遞歸左右子樹root->left=build(head,left,mid-1);root->right=build(head,mid+1,right);return root;
}

1.4BST轉換為中序序列鏈表

• 將樹按照中序遍歷，遍歷結果放在res中。為中序序列。
• 按照res構建鏈表。【next變成right】

void dfs(TreeNode* root, vector<int>& result){if(root==nullptr) return ;dfs(root->left,result);result.push_back(root->val);dfs(root->right,result);
}
TreeNode* increasingBST(TreeNode* root) {vector<int> res;dfs(root,res);TreeNode* dummy=new TreeNode(-1);TreeNode* p=dummy;for(int val:res){p->right=new TreeNode(val);p=p->right;}return dummy->right;
}

1.7BST的序列化和反序列化

• 序列化：BST先序遍歷——遍歷結果字符串
• 反序列化：遍歷結果字符串——BST

// 前序遍歷：根->左->右，將節點值拼接為字符串（用逗號分隔）
void preorder(TreeNode* node, string& result) {if (node == nullptr) return;// 拼接當前節點值if (!result.empty()) {result += ",";}result += to_string(node->val);// 遞歸遍歷左右子樹preorder(node->left, result);preorder(node->right, result);
}// 參考【先序序列構造BST】
TreeNode* buildBST(vector<int>& values, int start, int end) {}// Encodes a tree to a single string.
string serialize(TreeNode* root) {string result;preorder(root, result);return result;
}// Decodes your encoded data to tree.
TreeNode* deserialize(string data) {if (data.empty()) return nullptr;// 將字符串分割為整數列表（前序遍歷結果）vector<int> values;stringstream ss(data);string item;while (getline(ss, item, ',')) {values.push_back(stoi(item));}// 根據前序遍歷結果構建BSTreturn buildBST(values, 0, values.size() - 1);
}

1.6BST的種數

• 對于 i 個節點，我們可以選擇 j（1 ≤ j ≤ i）作為根節點
• 此時左子樹有 j-1 個節點，右子樹有 i-j 個節點
• 以 j 為根的二叉搜索樹數量 = 左子樹數量 × 右子樹數量，即 dp[j-1] × dp[i-j]
• 對所有可能的根節點求和，得到 dp[i]
  

int numTrees(int n) {vector<int> dp(n+1,0);dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){for(int j=1;j<=i;j++){dp[i] += dp[j-1] * dp[i-j];}}return dp[n];
}

上述題目是BST有幾種可能，下列代碼是BST的每一種可能都列舉出來。

// 生成[start, end]范圍內所有可能的BST
vector<TreeNode*> generate(int start, int end) {vector<TreeNode*> trees;// 遞歸終止條件：區間為空，返回空節點if (start > end) {trees.push_back(nullptr);return trees;}// 嘗試以每個數作為根節點for (int i = start; i <= end; ++i) {// 生成左右子樹vector<TreeNode*> leftTrees = generate(start, i - 1);vector<TreeNode*> rightTrees = generate(i + 1, end);// 組合左子樹和右子樹，形成以i為根的樹for (TreeNode* left : leftTrees) {for (TreeNode* right : rightTrees) {TreeNode* root = new TreeNode(i);root->left = left;root->right = right;trees.push_back(root);}}}return trees;
}
vector<TreeNode*> generateTrees(int n) {if (n == 0) return {};return generate(1, n);
}

二、BST的增刪改查

序號	題目	鏈接
1	驗證BST是否有效【中序序列】	https://leetcode.cn/problems/validate-binary-search-tree/solutions/2020306/qian-xu-zhong-xu-hou-xu-san-chong-fang-f-yxvh/?envType=problem-list-v2&envId=tree
2	查找值為val的節點	https://leetcode.cn/problems/search-in-a-binary-search-tree/?envType=problem-list-v2&envId=tree
3	插入1個節點	https://leetcode.cn/problems/insert-into-a-binary-search-tree/description/?envType=problem-list-v2&envId=tree
4	刪除1個節點	https://leetcode.cn/problems/delete-node-in-a-bst/description/?envType=problem-list-v2&envId=tree
5	恢復BST	https://leetcode.cn/problems/recover-binary-search-tree/description/?envType=problem-list-v2&envId=tree
6	修剪BST	https://leetcode.cn/problems/trim-a-binary-search-tree/description/?envType=problem-list-v2&envId=tree
7	平衡化	https://leetcode.cn/problems/balance-a-binary-search-tree/description/?envType=problem-list-v2&envId=tree

2.1驗證是否為BST

驗證所給的樹是否為有效的二叉搜索樹

二叉搜索樹的中序遍歷是有序的，且是升序的。【數組 or 遞歸 or 非遞歸】

• 解法1：將中序遍歷的結果放在數組中。比較【當前節點】與【當前節點的前一個節點】
• 解法2：pre 記錄中序遍歷序列中 “當前節點的前一個節點”。比較當前節點與 pre 的值。

bool isValidBST(TreeNode* root) {vector<int> inorder;// 中序遍歷inorderTraversal(root, inorder);// 檢查是否嚴格遞增for (int i = 0; i < inorder.size()-1; i++) {// 注意：必須嚴格小于，不能等于if (inorder[i+1] <= inorder[i]) return 0;}return 1;
}

TreeNode* pre=nullptr;
bool isValidBST(TreeNode* root) {if(root==nullptr) return 1;if(isValidBST(root->left)==false)  return 0;  //左if(pre!=nullptr && root->val <= pre->val){    //中return 0;}pre=root;return isValidBST(root->right);              //右
}

2.2查找值為val的節點

二叉樹的特性就是：左小右大。因此想在二叉樹中進行搜索某個值，可以進行比較。

• 如果val小于當前節點值——左子樹中繼續查找
• 如果val等于當前節點值——查找成功
• 如果val大于當前節點值——右子樹中繼續查找

TreeNode* searchBST(TreeNode* root, int val) {if(root==nullptr) return nullptr;if(root->val==val) return root;else if(val<root->val) return searchBST(root->left,val);else if(val>root->val) return searchBST(root->right,val);return nullptr;}

2.3插入一個值為val的節點

BST的性質：遞歸處理左子樹和右子樹

TreeNode* insertIntoBST(TreeNode* root, int val) {if (root == nullptr)  return new TreeNode(val);if (val < root->val)  root->left = insertIntoBST(root->left, val);else  root->right = insertIntoBST(root->right, val);return root;
}

2.4刪除一個值為val的節點

TreeNode* deleteNode(TreeNode* root, int key) {if(root==nullptr) return nullptr;// 查找目標節點if(key < root->val) root->left=deleteNode(root->left,key);else if(key > root->val) root->right=deleteNode(root->right,key);else{// 情況1：葉子節點，直接刪除if(root->left==nullptr && root->right==nullptr){delete root;return nullptr;}// 情況2：只有右子樹（修正指針指向）else if(root->left==nullptr){TreeNode* temp=root->right;  delete root;return temp;}// 情況3：只有左子樹（修正指針指向）else if(root->right==nullptr){TreeNode* temp=root->left;  delete root;return temp;}// 情況4：有左右子樹else{// 找到右子樹最小節點TreeNode* minNode=root->right;while(minNode->left!=nullptr){minNode=minNode->left;}// 替換當前節點值root->val=minNode->val;root->right=deleteNode(root->right, minNode->val);}}return root;
}

2.5恢復錯誤的兩節點

給你的根節點 root ，該樹中的 恰好 兩個節點的值被錯誤地交換。請在不改變其結構的情況下，恢復這棵樹 。

// 中序遍歷
void inorder(TreeNode* root) {if (root == nullptr) return;inorder(root->left); // 遍歷左子樹if (prev != nullptr && root->val < prev->val) {// 第一次發現逆序對，記錄前一個節點if (first == nullptr) first = prev;// 第二次發現逆序對（或相鄰交換的情況），記錄當前節點second = root;}prev = root;  // 更新前一個節點inorder(root->right); // 遍歷右子樹
}
void recoverTree(TreeNode* root) {inorder(root);swap(first->val, second->val);
}

2.6修剪BST

給你二叉搜索樹的根節點 root ，同時給定最小邊界low 和最大邊界 high。通過修剪二叉搜索樹，使得所有節點的值在[low, high]中。修剪樹 不應該 改變保留在樹中的元素的相對結構 。

• 若當前節點值 < low：左子樹所有值都 < low，直接用右子樹的修剪結果替換當前節點。
• 若當前節點值 > high：右子樹所有值都 > high，直接用左子樹的修剪結果替換當前節點。
• 若當前節點值在范圍內：保留該節點，遞歸修剪其左右子樹并重新連接。

TreeNode* trimBST(TreeNode* root, int low, int high) {if(root==nullptr) return nullptr;if(root->val < low) return trimBST(root->right,low,high);if(root->val > high) return trimBST(root->left,low,high);root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);return root;
}

2.7平衡化

• 對原 BST 進行中序遍歷，得到一個有序的節點值序列【參考樹的中序遍歷】
• 利用有序序列構建平衡 BST—— 通過選擇序列的中間元素作為根節點，左側元素構建左子樹，右側元素構建右子樹，確保左右子樹高度差不超過 1。【參考中序序列構造BST】

// 中序遍歷BST，獲取有序序列
void inorder(TreeNode* node, vector<int>& values) {if (node == nullptr) return;inorder(node->left, values);values.push_back(node->val);inorder(node->right, values);
}
// 從有序數組的[left, right]范圍構建平衡BST
TreeNode* buildBalancedBST(vector<int>& values, int left, int right) {if (left > right) return nullptr;//選擇中間元素作為根節點int mid = left + (right - left) / 2;TreeNode* node = new TreeNode(values[mid]);// 遞歸構建左右子樹node->left = buildBalancedBST(values, left, mid - 1);node->right = buildBalancedBST(values, mid + 1, right);return node;
}
TreeNode* balanceBST(TreeNode* root) {vector<int> values;inorder(root, values);return buildBalancedBST(values, 0, values.size() - 1);
}

三、BST的其他問題

序號	題目	鏈接
1	BST第K小的元素【中序第K元素】	https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=problem-list-v2&envId=tree
2	BST的眾數【哈希表】	https://leetcode.cn/problems/find-mode-in-binary-search-tree/description/?envType=problem-list-v2&envId=tree
3	BST中的兩數之和是否為target	https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/description/?envType=problem-list-v2&envId=tree
4	BST給定范圍的節點之和	https://leetcode.cn/problems/range-sum-of-bst/description/?envType=problem-list-v2&envId=tree
5	BST節點最小距離	https://leetcode.cn/problems/minimum-distance-between-bst-nodes/description/?envType=problem-list-v2&envId=tree
6	BST的最小絕對差【同上】	https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/?envType=problem-list-v2&envId=tree
7	二叉搜索樹轉換為累加樹	https://leetcode.cn/problems/convert-bst-to-greater-tree/description/?envType=problem-list-v2&envId=tree
8	BST的最近公共祖先【同二叉樹】	https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/description/?envType=problem-list-v2&envId=tree
9	最近節點查詢	https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/description/?envType=problem-list-v2&envId=tree

3.1第K小的元素

BST的中序序列是升序序列。因此中序遍歷遍歷整個樹，同時計數，遍歷到第K個的時候返回值。

int count = 0;  // 記錄當前遍歷到第幾個元素
int result = 0; // 存儲第k小的元素值
// 中序遍歷（左→根→右）
void inorder(TreeNode* root, int k) {if (root == nullptr) return;        inorder(root->left, k);// 先遍歷左子樹// 處理當前節點：計數+1，若達到k則記錄結果count++;if (count == k) {result = root->val;return; // 找到后可提前返回，無需繼續遍歷}inorder(root->right, k);// 再遍歷右子樹
}
int kthSmallest(TreeNode* root, int k) {inorder(root, k);return result;
}

3.2眾數

• 方法1（對于普通的二叉樹同樣適用）：遍歷整個二叉樹，在遍歷過程中，用哈希表記錄每個元素的個數，然后找到元素出現最多的次數記錄下來，并將該元素返回給結果。
• 方法2：搜索樹的中序遍歷是有序序列。利用這一個性質，

class Solution {
public:unordered_map<int,int> M;//遍歷并統計個數void f(TreeNode* root){if(root==nullptr) return;M[root->val]++;f(root->left);f(root->right);}vector<int> findMode(TreeNode* root) {vector<int> result;int count=1;if(root==nullptr) return result;f(root);//找到最大值for(auto m:M){if(m.second>count) count=m.second;}//填入resultfor(auto m:M){if(m.second==count) result.push_back(m.first);}return result;}
};

3.3兩數之和

給定一個二叉搜索樹 root 和一個目標結果 k，如果二叉搜索樹中存在兩個元素且它們的和等于給定的目標結果，則返回 true。

• BST按照中序遍歷，將結果存儲在result中。
• 利用雙指針快速定位目標。

vector<int> result;
void dfs(TreeNode* root){if(root==nullptr) return ;dfs(root->left);result.push_back(root->val);dfs(root->right);
}
bool findTarget(TreeNode* root, int k) {dfs(root);//利用雙指針，快速定位目標值int left=0;int right=result.size()-1;while(left<right){int sum=result[left]+result[right];if(sum==k) return 1;else if(sum<k) left++;else right--;}return 0;
}

3.4給定范圍的節點之和

給定二叉搜索樹的根結點 root，返回值位于范圍 [low, high] 之間的所有結點的值的和。

依然用BST的中序遍歷解決問題

int rangeSumBST(TreeNode* root, int low, int high) {if(root==nullptr) return 0;result.clear();dfs(root);int sum=0;for(int i=0;i<result.size();i++){if(result[i]>=low && result[i]<=high ) sum+=result[i];}return sum;
}

3.5節點最小距離

給你一個二叉搜索樹的根節點 root ，返回 樹中任意兩不同節點值之間的最小差值 。

轉換為中序有序序列之后計算。由于中序序列是有序的，因此離得越近，差值越小。

int minDiffInBST(TreeNode* root) {if(root==nullptr) return 0;result.clear();dfs(root);int m=INT_MAX;for(int i=0;i<result.size()-1;i++){m=min(m,result[i+1]-result[i]);}return m;}

3.6二叉搜索樹轉換為累加樹

• 二叉搜索樹的中序遍歷是一個單調遞增的有序序列。如果我們反序地中序遍歷該二叉搜索樹，即可得到一個單調遞減的有序序列。
• 只需要反序中序遍歷該二叉搜索樹，記錄過程中的節點值之和，并不斷更新當前遍歷到的節點的節點值，即可得到題目要求的累加樹。

int sum=0;
TreeNode* convertBST(TreeNode* root) {if(root==nullptr) return root;convertBST(root->right);sum+=root->val;root->val=sum;convertBST(root->left);return root;
}

3.7最近結果查詢

給你一個 二叉搜索樹 的根節點 root ，和一個由正整數組成、長度為 n 的數組 queries 。
請你找出一個長度為 n 的 二維 答案數組 answer ，其中 answer[i] = [mini, maxi] ：

• mini 是樹中小于等于 queries[i] 的 最大值 。如果不存在這樣的值，則使用 -1 代替。
• maxi 是樹中大于等于 queries[i] 的 最小值 。如果不存在這樣的值，則使用 -1 代替。
  返回數組 answer 。
  
• lower_bound 是 C++ 標準庫 頭文件中的一個二分查找函數，用于在有序序列中查找第一個大于等于目標值的元素，返回該元素的迭代器
• upper_bound：找第一個 > 目標值的元素（不包含等于的情況）。

中序遍歷序列為：[1,2,3,4,6,9,10]
查詢 q=5：
upper_bound找第一個 > 5 的元素是 6，前一個元素4→mini=4。
lower_bound找第一個≥5 的元素是 6→maxi=6。
結果為[4,6]。

// 中序遍歷BST，生成升序序列
void inorder(TreeNode* node, vector<int>& seq) {if (node == nullptr) return;inorder(node->left, seq);seq.push_back(node->val);inorder(node->right, seq);
}
vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {// 1.中序序列vector<int> inorderSeq;inorder(root, inorderSeq);vector<vector<int>> answer;for (int q : queries) {// 2. 對每個查詢，在有序序列中用二分查找找mini和maxiint mini = -1, maxi = -1;// 找mini：小于等于q的最大值（最后一個 <= q 的元素）auto it_mini = upper_bound(inorderSeq.begin(), inorderSeq.end(), q);if (it_mini != inorderSeq.begin()) {mini = *prev(it_mini);}// 找maxi：大于等于q的最小值（第一個 >= q 的元素）auto it_maxi = lower_bound(inorderSeq.begin(), inorderSeq.end(), q);if (it_maxi != inorderSeq.end()) {maxi = *it_maxi;}answer.push_back({mini, maxi});}return answer;
}