转载

[LeetCode] 96. Unique Binary Search Trees 不同的二叉搜索树 leetcode java

题目:

给定一个整数 n ，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

<strong>输入:</strong> 3
<strong>输出:</strong> 5
<strong>解释:
</strong>给定 <em>n</em> = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    /       /     /      / /      /
     3     2     1      1   3      2
    /     /       /                 /
   2     1         2                 3

思路：

当有n个节点时( 1 –n),任何一个数都可以当成根节点，左边j个节点，右边是n-j- 1 个节点所以就有nums[n] = nums[ 0 ]*nums[n]+nums[ 1 ]*nums[n- 1 ]+nums[ 2 ]*nums[n- 2 ]+ … +nums[n]*nums[ 0 ]; 因此我们需要先求出nums[ 0 ]–nums[n- 1 ] 最后返回nums[n]即可。

代码：

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

原文 http://www.lisite.top/2018/07/14/leetcode-96-unique-binary-search-trees-不同的二叉搜索树-leetcode-java/551.html

正文到此结束