不同的二叉搜索树

问题描述：

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

代码语言：javascript复制

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-binary-search-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解决方案

对于二叉树问题的一般解决思路为将该树分为根结点，左子树，右子树，然后再对左右子树各个击破，最终将信息返回到根结点。

定义一长度为n 1的整型数组记做dp,其中dp[i]表示长度为i时构成不同二叉搜索树的数目。

计算dp[i]时，分别计算以0~i-1元素为根结点构成二叉搜说树数目，再对其求和即为dp[i]。

计算以k为根结点的二叉搜索树的数目时为了保证BST定义约束，因此使用比他小的元素作为左子树，比他大的作为右子树。因此只需计算其左边元素构成BST的数目乘上右边元素构成BST的数目。

转移方程如下：

dp[i] = sum_{j=0}^{i-1}dp[j] * dp[i - 1 - j]

上述转移方程中dp[j]就为其左子树的数目，dp[i - 1 - j]为其右子树的数目。

baseline:

dp[0] = 1

代码如下：

代码语言：javascript复制

class Solution {
    public int numTrees(int n) {
        // dp[i] 为长度为i构成二叉搜索树的数目
        int[] dp = new int[n   1];
        dp[0] = 1;
        for(int i = 1; i <= n; i  ){
            // 依次加上以每个节点(j为下标)作为头结点的数目个数
            for(int j = 0; j < i; j  ){ 
                dp[i]  = dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];  
    }
}

二叉树 dp 搜索

0 人点赞