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

文章目录

• 数学补充
• 快速排序
• Code

数学补充

卡特兰数
https://baike.baidu.com/item/catalan/7605685?fr=aladdin

快速排序

把n个数按从小到大从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.不同的二叉搜索树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。