题目链接

LeetCode

题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

96. 不同的二叉搜索树** - 图1

输入： n = 3
输出： 5

示例 2：

输入： n = 1
输出： 1

提示：

  • 1 <= n <= 19

    解题思路

    方法一：动态规划（推荐）

    dp[n]表示 n 个节点的二叉搜索树个数，其中 dp[0] = dp[1] = 1
  1. 空树有一种
  2. 一个节点有一种
  3. 对于 n 个节点，根节点占一个，左子树的节点个数可以为0,1,2,3,4,….,n-1，对应的右子树的节点个数可以是n-1-0,n-1-1,n-1-2,….,0。当左节点有 i 个时，左子树二叉搜索树有 dp[i] 种，当右子树有 j 个时，右子树二叉搜索树有 dp[j] 种，其中 i+j+1 = n，当前左右分布 二叉搜索树有 dp[i] * dp[j] 种。递推公式为：

G(n)=∑G(i−1)⋅G(n−i) i=[0,n)

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         int[] dp = new int[n+1];
  4.         dp[0] = 1;
  5.         dp[1] = 1;
  6.         for(int i = 2; i <= n; ++i){
  7.             for(int j = 0; j< i;++j){
  8.                 // dp[j]为左边节点个数, dp[i - j - 1]为右边节点个数
  9.                 // j + (i - j - 1) + 1(根节点) == N
  10.                 dp[i] += (dp[j] * dp[i - j - 1]);
  11.             }
  12.         }
  13.         return dp[n];
  14.     }
  15. }
  • 时间复杂度 O(n^2)

  • 空间复杂度 O(n)

    方法二：数学法

    image.png

    class Solution {
  public int numTrees(int n) {
      long res = 1;
      for(int i = 0; i < n; ++i){
          res = res*2*(2*i+1)/(i+2);
      }
      return (int)res;
  }
}

  • 时间复杂度 O(n)

  • 空间复杂度 O(1)