[Leetcode] Unique Binary Search Trees 唯一二叉搜索树

阳光穿透心脏的1/2处 2022-02-16 10:45 190阅读 0赞

# Unique Binary Search Trees #

### I && II 解法请见：[https://yanjia.li/zh/2019/02/...][https_yanjia.li_zh_2019_02_...] ###

> 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

## 动态规划 ##

### 复杂度 ###

时间 O(N!) 空间 O(N)

### 思路 ###

二叉搜索树有个性质，就是左边的数都比根小，右边的数都比根大。另外，题目说明二叉树的节点是从1到n，所以我们能确定如果根为k，则根左边的数是1到k-1，根右边的数是k+1到n。还有一点技巧是，对于通过一个根来说，唯一二叉树的数量是其左子树的数量乘以右子树的数量，这是简单的乘法原理。并且，左右子树的形态数量是跟具体的数无关的，只跟这个树里有多少节点有关。而根可以选择从1到n的任意的数，唯一二叉树的总数，就是根为1到n的树相加。所以该问题化简为以k为根，其唯一左子树和右子树各有多少，这就是个动态规划的问题了。我们建立一个数组`dp[i]`，代表节点数为i的唯一子树有多少个。显然`dp[0]=dp[1]=1`。

### 代码 ###

public class Solution {
        public int numTrees(int n) {
            int[] dp = new int[n + 1];
            dp[0] = dp[1] = 1;
            //从节点数2开始计算到节点数为n的BST
            for(int i = 2; i < n + 1; i++){
                //计算根是第一个数的BST数量，直到根是最后一个数的BST数量，这里j可以理解为根左边的节点数
                for(int j = 0; j < i; j++){
                    //有n的节点的BST一共有 G(n)=F(1,n-1)+F(2,n-1)+...+F(n-1,n-1)个
                    //以i为根总共n个节点的BST有 F(i,n)=G(i-1)*G(i+1->n)个
                    //BST形态数量之和一共有多少个节点有关 G(i+1->n)=G(n-i)
                    //所以G(n)= G(0)*G(n-1)+G(1)*G(n-2)+...
                    dp[i] += dp[j] * dp[i - j - 1];
                }
            }
            return dp[n];
        }
    }

[https_yanjia.li_zh_2019_02_...]: https://yanjia.li/zh/2019/02/11/leetcode-unique-binary-search-trees-i-ii/