美文网首页
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