leetcode [96]Unique Binary Search Trees

佚名 7年前 (2019-04-10) 随笔 1778人围观抢沙发百度已收录

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input: 3
Output: 5
Explanation:
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

题目大意：

给定1到n这n个数字，找出n个数字所有可能的组成的二叉搜索树的个数。

解法：

采用动态规划的方法。当n=0的时候，二叉树可能的结构有1个，当n=1的时候，二叉树可能的结构也是1个。

假设dp[i]是表示有i个节点时，树可能的结构数。

举例分析，当n=5时，根节点有5种可能（1,2,3,4,5）

1.当根节点为1时，左子树为空，右子树的根节点有（2,3,4,5）四种可能，（2,3,4,5）相当于（1,2,3,4），dp[0]*dp[4]

2.当根节点为2时，左子树根节点有（1）一种可能，右子树的根节点有（3,4,5）三种可能，（3,4,5）相当于（1,2,3），dp[1]*dp[3]

3.当根节点为3时，左子树根节点有（1，2）两种可能，右子树的根节点有（4,5）两种可能，（4,5）相当于（1,2），dp[2]*dp[2]

4.当根节点为4时，左子树根节点有（1，2，3）三种可能，右子树的根节点有（5）一种可能，（5）相当于（1），dp[3]*dp[1]

5.当根节点为5时，左子树根节点有（1，2，3，4）四种可能，右子树为空，dp[4]*dp[0]

java:

class Solution {
    public int numTrees(int n) {
        int []G=new int[n+1];
        G[0]=G[1]=1;
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                G[i]+=G[j-1]*G[i-j];
            }
        }

        return G[n];
    }
}

这里的G[]就相当于是dp[]。