LeetCode No.96

LeetCode第九十六题—不同的二叉搜索树

自己代码的开源仓库:click here 欢迎Star和Fork :)

¶题目描述

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

示例:

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

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3
通过次数120,434提交次数173,199

¶代码+题目分析

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int

        上一道题的改编吧，这个什么鬼顺序，明明这道题前面比较好吧。除了直接把上一题的结果返回一个len之外的别的办法
        直接改变上一题的方法有点蠢，必然花费时间很大。因此考虑其他办法
        考虑使用动态规划
        思路：
            同上一题的思路：如果1-n中，第k个节点去作为根节点划分，那么1-k-1则进行构建左子搜索树，k+1-n则构建右子搜索树
            对于左子树同样重复上述方法进行划分，同样右子树也是重复上述方法进行划分
            假设左子树有a种形态，右子树有b种形态，则以k为根节点的搜索树则有a*b种形态

        定义DP问题：
            n=2时，用1，2构建搜索树，以1为根，则用2只能构建一种搜索树，以2为根，则用1只能构建一种搜索树
            1        2
             \      /
              2    1
            n=3时，用1,2,3构建搜索树，以1为根，针对2，3的话类似上面会有两种结果，
                                   以2为根，针对1左子树，3右子树，只有一种结果，
                                   以3为根，针对1，2的话类似上面会有两种结果
            n=4时，用1，2，3，4构建搜索树，以1为根，根据n=3的结果，有5种结果
                                       以2为根，左子树一种结结果，右子树3，4有两种结果
                                       以3为根，左子树两种结果，右子树一种结果
                                       以4为根，左子树5种结果
            对于n=5，n=6都类似。  其实感觉通过递推可以直接找到规律了
            因此dp[i]可以用来表示为连续的i个数构成的搜索树的个数 比如i=2 则是1，2或者2，3或者3，4等只能构成2个数
        状态转移方程：
            这里我们依次要用1-n分别作为根节点来构建状态转移方程。去掉根节点之后左右两侧的节点分别用于构建左子树和右子树
            根据上面dp[i]的定义我们可以得到下述方程:
            dp[i]是连续i个数可以构成的子树的个数
            dp[i] = ∑ dp[j]*dp[i-j-1] // 求和是用来除以j从0到i-1所有的情况，-1的目的是因为有一个节点要作为根节点
        """
        # 处理特殊情况
        if n == 0 or n == 1:
            return 1
        # 正常遍历
        dp = [0]*(n+1) # 创建数组
        # 只有 1个或者0个节点智能生成一棵树
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            for j in range(0,i):
                dp[i] += dp[j] * dp[i-j-1] # 状态转移方程
        
        return dp[-1]