描述

• 已知一棵节点个数为 的二叉树的中序遍历单调递增, 求该二叉树能能有多少种树形, 输出答案对 10⁹+7取模
  示例1
  输入：1
  返回值：1
  示例2
  输入：2
  返回值：2
  示例3
  输入：4
  返回值：14
  备注：

  方法一

  思路

• 递归

• 首先介绍一个数学知识，两数乘积之模等于两数模之乘积；对证明感兴趣的同学可以百度。

• 我们容易知道当n = 1时，满足条件的二叉树形状只有一个，当n = 2时有两个；

• 当n = 3时，有以下的形状：
  

• 可以看见当根节点为1时，所有节点均只能在右子树中，且数量为2，当根节点为3时所有节点均只能在左子树中，且形状数量为2，当根节点为2时，小于2的在左子树，大于2的在右子树，且形状数量为1。

• 再回过头来看题目要求，升序的中序序列，是不是有点像一个二叉排序树，左子树的所有节点均小于根节点，右子树的所有节点均大于根节点，所以本题实际上是求节点数为n的二叉排序树的形状数量。

• 故对于一个节点数为n的二叉排序树，当根节点值为i时，左子树有i-1个节点，右子树有n-i-1个节点，且左子树与右子树均为二叉排序树，所以当根节点值为i时，二叉排序树总共有种形状当然需要取模，那么对于一个节点数为n的二叉排序树其形状数量为

  

• 当二叉树节点数为0时，默认为1，便于计算，所以可以依据上述公式，递归计算给定数量的二叉排序树的形状数。

• 代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    private static int mod = 1000000007;
    public int numberOfTree (int n) {
        long count = calculate(n);
        return (int)(count % mod);
    }
    private long calculate(int n){
        // n为0返回1
        if (n == 0){
            return 1;
        }
        // 直接返回
        if (n == 1 || n == 2){
            return n;
        }
        long count = 0;
        // 递归计算子二叉树的树形个数
        for (int i = 1;i <= n;++i){
            count = count + calculate(n-i)*calculate(i-1);
            count = count % mod;
        }
        return count;
    }
}

• 时间复杂度：，递归计算每次递归都要经历一重循环；
• 空间复杂度：,递归调用栈深度为n。

方法二

思路

• 动态规划，记忆表。
• 方法一的时间复杂度过大，运行超时，且其计算过程中会有很多冗余计算，譬如说计算f(4)，其需要重复计算f(3),f(2),f(1)……，故可以使用记忆表，记录计算过程中各个节点数具有的二叉排序树的形状数量。
• 创建dp数组，借助方法一的递推公式进行计算。
• 在计算过程中直接取模，避免乘法溢出。
• 代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    private static int mod = 1000000007;
    public int numberOfTree (int n) {
        // 直接返回
        if (n == 1 || n == 2){
            return n;
        }
        long[] dp = new long[n+1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3;i < dp.length;++i){
            long count = 0;
            for (int j = 1;j <= i;++j){
                count += ((dp[i-j]*dp[j-1])%mod);
            }
            dp[i] = (int) (count % mod);
        }

        return (int) dp[n];
    }

• 时间复杂度:,双重循环；
• 空间复杂度：，一维数组辅助运算。