首页 > 代码库 > leetcode - Unique Binary Search Trees

leetcode - Unique Binary Search Trees

2024-07-08 07:05:34   212人阅读

题目：Unique Binary Search Trees

Given n, how many structurally unique BST‘s (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST‘s.

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

个人思路：

1、二叉搜索树的中序遍历是有序的（从小到大），这里是1-n，那么我就从1-n遍历根节点，将每个情况下的BST个数相加，便是结果

2、根节点左边的便是左子树，右边的便是右子树，再用相同的方法去处理左右子树，左子树的个数乘以右子树的个数便是以该节点为根节点的BST的个数，这是一个递归的过程，递归的基本条件是空树的情况返回1

代码：

 1 #include <iostream> 2  3 class Solution 4 { 5 public: 6     int numTrees(int n) 7     { 8         int num = 0; 9 10         for (int i = 1; i <= n; ++i)11         {12             num += partNumTrees(1, i - 1) * partNumTrees(i + 1, n);13         }14 15         return num;16     }17 private:18     int partNumTrees(int start, int end)19     {20         if (start > end)21         {22             return 1;23         }24 25         int num = 0;26         for (int i = start; i <= end; ++i)27         {28             num += partNumTrees(start, i - 1) * partNumTrees(i + 1, end);29         }30 31         return num;32     }33 };34 35 int main()36 {37     Solution s;38     std::cout << s.numTrees(4) << std::endl;39     system("pause");40 41     return 0;42 }
View Code

 

按照惯例，上网搜寻更优的算法，发现有利用动态规划思想解决该问题的算法，链接：http://www.blogjava.net/menglee/archive/2013/12/20/407801.html

思路：

1、先开辟一个n+1大小的数组dp，dp[i]记录了有i个节点的BTS的个数，这样就可以在需要时直接读取数值，而不是当场去计算，用空间换取时间

2、主要目的是要计算出dp[n]，可从dp[2]开始计算，先预设几个dp初值，如dp[0]=1,dp[1]=1等，计算dp[i]的思路与我上面的思路相同

代码：

 1 #include <iostream> 2  3 class Solution 4 { 5 public: 6     int numTrees(int n) 7     { 8         /* 9         int num = 0;10 11         for (int i = 1; i <= n; ++i)12         {13             num += partNumTrees(1, i - 1) * partNumTrees(i + 1, n);14         }15         */16 17         int *dp = new int[n + 1];18         dp[0] = 1;19         dp[1] = 1;20 21         for (int i = 2; i <= n; ++i)22         {23             int tmp = 0;24             for (int j = 1; j <= i; ++j)25             {26                 tmp += dp[j - 1] * dp[i - j];27             }28             dp[i] = tmp;29         }30 31         return dp[n];32     }33 private:34     /*35     int partNumTrees(int start, int end)36     {37         if (start > end)38         {39             return 1;40         }41 42         int num = 0;43         for (int i = start; i <= end; ++i)44         {45             num += partNumTrees(start, i - 1) * partNumTrees(i + 1, end);46         }47 48         return num;49     }50     */51 };52 53 int main()54 {55     Solution s;56     std::cout << s.numTrees(4) << std::endl;57     system("pause");58 59     return 0;60 }
View Code

 

 


联系
我们