不同的二叉搜索树

一、题目描述

题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees/

 

二、题目分析

本题可使用动态规划方法解决。

首先要意识到，节点的序号对二叉树的构建是等价的，即假如我们分别用1，2和3，4构建搜索二叉树，能构建的数量都是2。因此，我们只要确定了根节点，比根节点小的为左子树，比根节点大的为右子树，而直到了左右节点子树的节点数量，就可以通过dp得到左右子树分别由多少种情况，再将左右子树情况数相乘就可以得到以当前节点为root的二叉搜索树数量。

 

三、代码

    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        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];
    }