题目描述(中等难度)

96. Unique Binary Search Trees - 图1

95 题一样,只不过这道题不需要输出所有的树,只需要输出所有可能的二分查找树的数量。所以完全按照 95 题思路写,大家可以先到 95 题看一看。

解法一 递归

下边是 95 题的分析。

我们可以利用一下查找二叉树的性质。左子树的所有值小于根节点,右子树的所有值大于根节点。

所以如果求 1…n 的所有可能。

我们只需要把 1 作为根节点,[ ] 空作为左子树,[ 2 … n ] 的所有可能作为右子树。

2 作为根节点,[ 1 ] 作为左子树,[ 3…n ] 的所有可能作为右子树。

3 作为根节点,[ 1 2 ] 的所有可能作为左子树,[ 4 … n ] 的所有可能作为右子树,然后左子树和右子树两两组合。

4 作为根节点,[ 1 2 3 ] 的所有可能作为左子树,[ 5 … n ] 的所有可能作为右子树,然后左子树和右子树两两组合。

n 作为根节点,[ 1… n ] 的所有可能作为左子树,[ ] 作为右子树。

至于,[ 2 … n ] 的所有可能以及 [ 4 … n ] 以及其他情况的所有可能,可以利用上边的方法,把每个数字作为根节点,然后把所有可能的左子树和右子树组合起来即可。

如果只有一个数字,那么所有可能就是一种情况,把该数字作为一棵树。而如果是 [ ],那就返回 null。

对于这道题,我们会更简单些,只需要返回树的数量即可。求当前根的数量,只需要左子树的数量乘上右子树。

  1. public int numTrees(int n) {
  2. if (n == 0) {
  3. return 0;
  4. }
  5. return getAns(1, n);
  6. }
  7. private int getAns(int start, int end) {
  8. int ans = 0;
  9. //此时没有数字,只有一个数字,返回 1
  10. if (start >= end) {
  11. return 1;
  12. }
  13. //尝试每个数字作为根节点
  14. for (int i = start; i <= end; i++) {
  15. //得到所有可能的左子树
  16. int leftTreesNum = getAns(start, i - 1);
  17. //得到所有可能的右子树
  18. int rightTreesNum = getAns(i + 1, end);
  19. //左子树右子树两两组合
  20. ans+=leftTreesNum * rightTreesNum;
  21. }
  22. return ans;
  23. }

受到这里的启发,我们甚至可以改写的更简单些。因为 95 题要把每颗树返回,所有传的参数是 start 和 end。这里的话,我们只关心数量,所以不需要具体的范围,而是传树的节点的数量即可。

  1. public int numTrees(int n) {
  2. if (n == 0) {
  3. return 0;
  4. }
  5. return getAns(n);
  6. }
  7. private int getAns(int n) {
  8. int ans = 0;
  9. //此时没有数字或者只有一个数字,返回 1
  10. if (n==0 ||n==1) {
  11. return 1;
  12. }
  13. //尝试每个数字作为根节点
  14. for (int i = 1; i <= n; i++) {
  15. //得到所有可能的左子树
  16. // i - 1 代表左子树节点的数量
  17. int leftTreesNum = getAns(i-1);
  18. //得到所有可能的右子树
  19. //n - i 代表左子树节点的数量
  20. int rightTreesNum = getAns(n-i);
  21. //左子树右子树两两组合
  22. ans+=leftTreesNum * rightTreesNum;
  23. }
  24. return ans;
  25. }

然后,由于递归的分叉,所以会导致很多重复解的计算,所以使用 memoization 技术,把递归过程中求出的解保存起来,第二次需要的时候直接拿即可。

  1. public int numTrees(int n) {
  2. if (n == 0) {
  3. return 0;
  4. }
  5. HashMap<Integer,Integer> memoization = new HashMap<>();
  6. return getAns(n,memoization);
  7. }
  8. private int getAns(int n, HashMap<Integer,Integer> memoization) {
  9. if(memoization.containsKey(n)){
  10. return memoization.get(n);
  11. }
  12. int ans = 0;
  13. //此时没有数字,只有一个数字,返回 1
  14. if (n==0 ||n==1) {
  15. return 1;
  16. }
  17. //尝试每个数字作为根节点
  18. for (int i = 1; i <= n; i++) {
  19. //得到所有可能的左子树
  20. int leftTreesNum = getAns(i-1,memoization);
  21. //得到所有可能的右子树
  22. int rightTreesNum = getAns(n-i,memoization);
  23. //左子树右子树两两组合
  24. ans+=leftTreesNum * rightTreesNum;
  25. }
  26. memoization.put(n, ans);
  27. return ans;
  28. }

解法二 动态规划

直接利用95题解法三的思路,讲解比较长就不贴过来了,可以过去看一下。

或者直接从这里的解法一的思路考虑,因为递归是从顶层往下走,压栈压栈压栈,到了长度是 0 或者是 1 就出栈出栈出栈。我们可以利用动态规划的思想,直接从底部往上走。求出长度是 0,长度是 1,长度是 2….长度是 n 的解。用一个数组 dp 把这些结果全部保存起来。

  1. public int numTrees(int n) {
  2. int[] dp = new int[n + 1];
  3. dp[0] = 1;
  4. if (n == 0) {
  5. return 0;
  6. }
  7. // 长度为 1 到 n
  8. for (int len = 1; len <= n; len++) {
  9. // 将不同的数字作为根节点,只需要考虑到 len
  10. for (int root = 1; root <= len; root++) {
  11. int left = root - 1; // 左子树的长度
  12. int right = len - root; // 右子树的长度
  13. dp[len] += dp[left] * dp[right];
  14. }
  15. }
  16. return dp[n];
  17. }

参考这里还有优化的空间。

利用对称性,可以使得循环减少一些。

  • n 是偶数的时候 1 2 | 3 4 ,for 循环中我们以每个数字为根求出每个的解。我们其实可以只求一半,根据对称性我们可以知道 1 和 4,2 和 3 求出的解分别是相等的。

  • n 是奇数的时候

    1 2 | 3 | 4 5,和偶数同理,只求一半,此外最中间的 3 的解也要加上。

  1. public int numTrees6(int n) {
  2. if (n == 0) {
  3. return 0;
  4. }
  5. int[] dp = new int[n + 1];
  6. dp[0] = 1;
  7. dp[1] = 1;
  8. // 长度为 1 到 n
  9. for (int len = 2; len <= n; len++) {
  10. // 将不同的数字作为根节点,只需要考虑到 len
  11. for (int root = 1; root <= len / 2; root++) {
  12. int left = root - 1; // 左子树的长度
  13. int right = len - root; // 右子树的长度
  14. dp[len] += dp[left] * dp[right];
  15. }
  16. dp[len] *= 2;// 利用对称性乘 2
  17. // 考虑奇数的情况
  18. if ((len & 1) == 1) {
  19. int root = (len >> 1) + 1;
  20. int left = root - 1; // 左子树的长度
  21. int right = len - root; // 右子树的长度
  22. dp[len] += dp[left] * dp[right];
  23. }
  24. }
  25. return dp[n];
  26. }

解法三 公式法

参考这里-timesO(1)space>)。其实利用的是卡塔兰数列,这是第二次遇到了,之前是第 22 题 ,生成合法的括号序列。

这道题,为什么和卡塔兰数列联系起来呢?

看一下卡塔兰树数列的定义:

令h ( 0 ) = 1,catalan 数满足递推式:

h ( n ) = h ( 0 ) * h ( n - 1 ) + h ( 1 ) * h ( n - 2 ) + … + h ( n - 1 ) * h ( 0 ) ( n >=1 )

例如:h ( 2 ) = h ( 0 ) * h ( 1 ) + h ( 1 ) * h ( 0 ) = 1 * 1 + 1 * 1 = 2

h ( 3 ) = h ( 0 ) * h ( 2 ) + h ( 1 ) * h ( 1 ) + h ( 2 ) * h ( 0 ) = 1 * 2 + 1 * 1 + 2 * 1 = 5

再看看解法二的算法

  1. public int numTrees(int n) {
  2. int[] dp = new int[n + 1];
  3. dp[0] = 1;
  4. if (n == 0) {
  5. return 0;
  6. }
  7. // 长度为 1 到 n
  8. for (int len = 1; len <= n; len++) {
  9. // 将不同的数字作为根节点,只需要考虑到 len
  10. for (int root = 1; root <= len; root++) {
  11. int left = root - 1; // 左子树的长度
  12. int right = len - root; // 右子树的长度
  13. dp[len] += dp[left] * dp[right];
  14. }
  15. }
  16. return dp[n];
  17. }

完美符合,而卡塔兰数有一个通项公式。

96. Unique Binary Search Trees - 图2

注:

96. Unique Binary Search Trees - 图3

代表

96. Unique Binary Search Trees - 图4

化简一下上边的公式

96. Unique Binary Search Trees - 图5

所以用一个循环即可。

  1. int numTrees(int n) {
  2. long ans = 1, i;
  3. for (i = 1; i <= n; i++)
  4. ans = ans * (i + n) / i;
  5. return (int) (ans / i);
  6. }

上道题会了以后,这道题很好写。解法二中利用对称的优化,解法三的公式太强了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话,可以点击 这里 给一个 star 哦 ^^

如果想系统的学习数据结构和算法,强烈推荐一个我之前学过的课程,可以点击 这里 查看详情