Leetcode树——不同的二叉搜索树（C++）

题目描述

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-binary-search-trees 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

今天首先用递归的思路解题，即可以分别考虑以1~n的每个数为根节点，只需找到左子树x节点的不同二叉搜索树个数和右子树y个节点的不同二叉搜索次数，直到节点数为0/1，则返回1。代码实现起来很简单：

class Solution { public: int numTrees(int n) { if(n<2) return 1; else{ int i,sum=0,left,right; for(i=0;i<n;i++){ left=i; right=n-i-1; sum += numTrees(left)*numTrees(right); } return sum; } } };

但是嗷！递归函数是真的慢： 竟然超出了时间限制。。。。 由于递归函数会对相同的n值反复计算多次，造成时间上的浪费，这里稍微用点蠢方法缩短一下时间：

class Solution { public: int numTrees(int n) { if(n<2) return 1; else if(n==3)//这和直接列答案没什么区别呜呜呜呜 return 5; else if(n==4) return 14; else if(n==5) return 42; else{ int i,sum=0,left,right; for(i=0;i<n;i++){ left=i; right=n-i-1; sum += numTrees(left)*numTrees(right); } return sum; } } };

运行通过了，但是效率真的差： 这里其实很想实现一种动态的数组，记录下在递归过程中得到的每个节点对应的不同二叉搜索树个数，避免对相同节点个数进行重复计算。这里利用数组再重新定义了一个函数，代码如下:

class Solution { public: int count(int n,int a[]){//用于递归求不同二叉搜索树个数的函数，a存储0~n个节点对应不同二叉搜索树的个数 if(a[n]!=0)//如果数组中已存储了该节点个数的不同二叉搜索树个数，则直接返回。 return a[n]; else{ int i,sum=0,left,right; for(i=0;i<n;i++){ left=i; right=n-i-1; sum += count(left,a)*count(right,a); } a[n] = sum; return sum; } } int numTrees(int n) { int a[n+1]; for(int i=0;i<=n;i++){ // 初始化存储个数的数组。 if(i<2) a[i] =1; else a[i]=0; //未计算的，直接赋值为0. } return count(n,a); } };

运行结果如下: 这个运行速度也是惊到我了哈哈！但是空间复杂度还有进步的空间嘤嘤嘤。据说这道题也是动态规划类型的，晚上再学习一下题解~