美文网首页
96. Unique Binary Search Trees

96. Unique Binary Search Trees

作者: HalcyonMoon | 来源:发表于2016-06-29 11:57 被阅读0次

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
public class Solution {
    public int numTrees(int n) {
        int dp[] = new int[n+1];
        dp[0] = 1;
        for(int i = 1; i<=n; i++){
            for(int j = 0 ; j< i; j++){
                dp[i] += dp[j]*dp[i-j-1];
            }
        }
        return dp[n];
    }
}

相关文章

网友评论

      本文标题:96. Unique Binary Search Trees

      本文链接:https://www.haomeiwen.com/subject/fbxxjttx.html