96. 不同的二叉搜索树

女爷i 2022-12-23 06:18 291阅读 0赞

题目来源

96. 不同的二叉搜索树

题目描述

在这里插入图片描述

题目解析

动态规划

假设n个节点存在二叉排序树的个数是G(n)，令f(i)是以i为根的二叉搜索树的个数，则有

G ( n ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + . . . f ( n ) G(n)=f(1)+f(2)+f(3)+…f(n) G(n)=f(1)+f(2)+f(3)+…f(n)

n为根节点，当i为根节点时，其左子树节点个数为[1,2,3...i-1]，右子树节点个数为[i+1, i+2，... n]，所以当i为根节点时，其左子树节点个数为i-1个，右子树节点为n-i个，即f(i) = G(i-1)*G(n-i)。因此
G ( n ) = G ( 0 ) ∗ G ( n − 1 ) + G ( 1 ) ∗ G ( n − 2 ) + . . . + G ( n − 1 ) ∗ G ( 0 ) G(n) = G(0)*G(n-1)+G(1)*G(n-2)+…+G(n-1)*G(0) G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+…+G(n−1)∗G(0)

  1. class Solution {
  3. public int numTrees(int n) {
  5.         int [] ints = new int[n + 1];
  6.         ints[0] = 1;
  7.         ints[1] = 1;
  8.         for (int i = 2; i <= n; i++){
  10.             for (int j = 1; j <= i; j++){
  12.                 ints[i] += ints[j - 1] * ints[i - j];
  13.             }
  14.         }
  16.         return ints[n];
  17.     }
  18. }

发表评论

表情：
评论列表 （有 0 条评论，291人围观）

还没有评论，来说两句吧...

相关阅读