LeetCode96-不同的二叉搜索树

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/unique-binary-search-trees/

中文链接：https://leetcode-cn.com/problems/unique-binary-search-trees/

题目详述

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

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

题目详解

动态规划。

  • 由于二叉树不同的根结点构成的二叉搜索树不同，对于以 1 … n 为结点组成的二叉搜索树，可以分别以结点 1 … n 作为根结点。
  • 以 i 作为二叉搜索树根结点，则它的左子树有 numTrees(i - 1) 种，它的右子树有 numTrees(n - i) 种，整棵树有 numTrees(i - 1) * numTrees(n - i) 种。
  • 则 numTrees(n) = numTrees(0) * numTrees(n - 1) + ...。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00096 {
    
    public int numTrees(int n) {
        if (n < 2) {
            return 1;
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            res += numTrees(i - 1) * numTrees(n - i);
        }
        return res;
    }
}

上面是直接进行搜索，存在很多重复计算，会超时，可以改为动态规划。

  • 外层循环代表从 dp[1] 推进到 dp[n]。
  • 内层循环用于计算当前 dp[i]。
1
2
3
4
5
6
7
8
9
10
11
12
13
public class LeetCode_00096 {

    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}