[leetcode-动态规划]--96. Unique Binary Search Trees

阳光穿透心脏的1/2处 2022-07-12 04:23 145阅读 0赞

Question 96. 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

> 中文：给定一个非负整数n，使用 1~n 能够构造多少种不同的二叉查找树。

比如n=3时，对于以1为根的树的个数等于左子树的个数乘以右子树的个数，左子树是0个元素的树，右子树是2个元素的树。 以2为根的树的个数等于左子树的个数乘以右子树的个数，左子树是1个元素的树，右子树也是1个元素的树。

当数组为\[1,2,….n\]时， 基于以下原则构建BST树具有唯一性： 以i为根节点的树，其左子树由\[1, i-1\]构造成，其右子树由\[i+1, n\] 构造成。

定义f(i) 为以\[1, i\]能产生的Unique Binary Search Tree的数目，则  
如果数组为空，则只有一种BST，也就是空树，f(0)=1;  
如果数组仅有一个元素1， 只有一种BST，单个根节点， f(1)=1；  
如果数组有两个元素1，2那么有两种可能：

1         2
      \       /
       2     1

f(2) = f(0)\*f(1) 1为根的情况  
\+f(1)\*f(0) 2为根的情况

再看一下有3个元素的数组，发现BST取值方式如下：  
f(3) = f(0)\*f(2) 1为根的情况  
\+f(1)\*f(1) 2为根的情况  
\+f(2)\*f(0) 3为根的情况

由此可递推出公式：  
![这里写图片描述][SouthEast]

列出来就是：

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

下面给出实现代码：

public static int numTrees(int n) {
        int [] f = new int[n+1];//利用f[n]来存储最后的结果.
        f[0] = f[1] = 1;
    
        for(int i=2; i<=n; ++i) {
            for(int j=1; j<=i; ++j) {
                f[i] += f[j-1] * f[i-j];
            }
        }
        return f[n];
    }

完整代码的github地址：  
[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question96.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question96.java]

[SouthEast]: /images/20220711/a4f2c447839447eeb0a6e2c412ac55ab.png
[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Question96.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Question96.java