首先分析一下什么是二叉搜索樹。因為我本科學習數據結構的時候就是單純背了一下題庫，考試非常簡單。現在額外補充學一些之前自己沒有學過的內容。有序向量可以二分查找，列表可以快速插入和刪除。二叉搜索樹可以實現按照關鍵碼訪問。call by key .數據表現為詞條，這可能和現實聯系更加緊密。比如說，我們在 csdn 里面搜索信息，一般都是搜索關鍵字。然后我們學習，很可能也是第一反應是一些關鍵字。之前寫的堆排序，感覺有點像二叉搜索樹，但是好像是優先隊列。我這壓根就不是復習，是學習。嗚嗚嗚。我太喜歡和別人交流具體知識點了，尤其是我擅長的東西。那些不擅長的東西，希望自己能盡快擅長起來。因為這真的比較重要。中序遍歷可以把標準的二叉樹垂直映射到 x 軸，所以二叉樹的查找類似于向量的二分查找。中序遍歷的順序是左子樹，根，右子樹。這個就是，輸入一個需要查找的元素 e ，然后 e 比當前遍歷到的元素小，就遍歷到左子樹。假設 e 比當前的遍歷到的元素大，就遍歷到右子樹。這里有一個前提，就是認為，左子樹是更小的元素，右子樹是更大的元素。太難了。不研究了。

直接在算法題里面體會得了。二叉搜索樹要求左子樹小于等于根節點，右子樹大于等于右子樹。能不能取到等號，問一下 deepseek 。標準的 bst 是不能取到等號的。

對于 n 個節點生成的二叉搜索樹的數量是 catalan(n) ,感覺時間復雜度分析考試應該不會考，算了。不學了。算了，感覺可以記一下，深入研究比較有意思。生成一棵二叉搜索樹需要線性的時間，總共有 catalan(n) 棵二叉搜索樹，所以時間復雜度是 O(n*catalan(n)) ，$$catalan(n)=\frac{(2n)!}{n!(n+1)!}$$ ，查了一下，是做了一個近似處理，然后得到的卡特蘭數的增長速度，其實就是第 n 個卡特蘭數的近似表示，$$\frac{4^n}{n^{\frac{3}{2}}?\sqrt{\pi }}$$

數學公式這么寫出來真帥啊！時間復雜度和空間復雜度均是 $$O(\frac{4^n}{n^{\frac{1}{2}}})$$

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<TreeNode*> generateTrees(int start,int end){if(start>end){return {nullptr};}vector<TreeNode*> allTrees;for(int i=start;i<=end;i++){vector<TreeNode*> leftTrees=generateTrees(start,i-1);vector<TreeNode*> rightTrees=generateTrees(i+1,end);for(auto& left:leftTrees){for(auto& right:rightTrees){TreeNode* currTree=new TreeNode(i);currTree->left=left;currTree->right=right;allTrees.emplace_back(currTree);}}}return allTrees;}vector<TreeNode*> generateTrees(int n) {if(!n){return {};}return generateTrees(1,n);}
};