163. 不同的二叉查找树 

 

给出 n，问由 1...n 为节点组成的不同的二叉查找树有多少种？

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出n = 3，有5种不同形态的二叉查找树：

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

int NumTrees::numTrees(int n) {    /*     * 解题思路:二叉树递归的原则思路     * 1.3个可以看做是左子树2个 右子树2个 和左右子树分别一个相乘 2*0+1*1+0*2     * 2.4个可以看做做树 固定1个  左3 右1 左2 右2  左1 右3 3*0+1*2+2*1+0*3     * */    // write your code here    if (n <= 0) {        return 1;    }    vector
         
           dp(n + 1, 0);    dp[0] = dp[1] = 1;    for (int i = 2; i <= n; i++) {        for (int j = 1; j <= i; j++) {            dp[i] += dp[j - 1] * dp[i - j];        }    }    return dp[n];}