Problem: 96. 不同的二叉搜索樹

文章目錄

• 數(shù)學補充
• 快速排序
• Code

數(shù)學補充

卡特蘭數(shù)
https://baike.baidu.com/item/catalan/7605685?fr=aladdin

快速排序

把n個數(shù)按從小到大從1到n編號，則這個形成的所有二叉樹就是快速排序的所有情況

可以看出來快排的最壞時間復雜度為$On$，即二叉樹為單鏈表時

最好復雜度即兩邊均勻分布，$Olo{g}_{2}n$

這與二叉搜索樹的性質：中序遍歷為有序序列不謀而合

Code

class Solution { public://快速排序的最好復雜度和最壞復雜度int dfs(int n,vector<int>& trees_num){if(trees_num[n]!=0) return trees_num[n];int tmp=0;for(int i=0;i<n;i++)tmp=tmp+dfs(n-1-i,trees_num)*dfs(i,trees_num);trees_num[n]=tmp;return tmp;}int numTrees(int n) {vector<int> trees_num(25);trees_num[0]=1;trees_num[1]=1;// trees_num[2]=2;// trees_num[3]=5;return dfs(n,trees_num);} };

總結

以上是生活随笔為你收集整理的力扣96.不同的二叉搜索树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。