题解 | #二叉树的个数#

题目描述
已知一棵节点个数为n的二叉树的中序遍历单调递增，求该二叉树能能有多少种树形,输出答案取模10^9+7

方法一：递归求解

求解思路
对于本题目，因为题目给出一颗节点个数为n的二叉树的中序遍历单挑递增的条件，我们任意取一个节点为根节点，然后左子树的树形数目加上右子树的树形数目即为题目所要求的总的树形数目。但是由于普通递归会有很多重复情况，我们声明一个用来记录重复情况的数组，当数组的值不为0时，递归直接返回。

图片说明

解题代码

import java.util.*;
public class Solution {
    int mod=1000000007; // 常数
    long[] mymemo; // 记录数组
    public int numberOfTree (int n)
    {
        mymemo=new long[n+1];
        return (int)dfs(n);
    }
    private long dfs(int n)
    {
        if(mymemo[n]!=0) return mymemo[n];
        if(n==0||n==1) return 1;
        long myres=0;
        for(int i=1;i<=n;i++)
        {   //左子树情况
            long left=dfs(i-1);
            //右子树情况
            long right=dfs(n-i);
            myres=(myres+left*right)%mod; // 更新结果
        }
        mymemo[n]=myres;
        return myres; // 返回结果
    }
}

复杂度分析
时间复杂度：根据树的形状，并且使用递归，因此时间复杂度为 $图片说明$
空间复杂度：使用容量为n的栈空间，因此空间复杂度为 $O(N)$

方法二：动态规划--优化求解

求解思路
对于本题目我们也可以采用动态规划的思想，令dp[i]表示有i个节点时共有多少种树形。并且当节点数为空或者只有一个节点时树形为1.最后我们写出来状态转移方程为：
图片说明

图片说明

解题代码

import java.util.*;
public class Solution {
    int mod=1000000007; // 常数
    public int numberOfTree (int n) 
    {   //初始化dp数组
        long[] mydp=new long[n+1];
        mydp[0]=1; // 赋初值
        mydp[1]=1; // 赋初值
        for(int i=2;i<=n;i++)
        {   //找到每一个节点为根的情况
            for(int j=1;j<=i;j++)
            {
                mydp[i] = (mydp[i]+mydp[j-1]*mydp[i-j])%mod; // 状态转移方程
            }
        }
        return (int)mydp[n]; // 返回结果
    }
}

复杂度分析
时间复杂度：根据状态转移方程，可知时间复杂度为 $图片说明$
空间复杂度：需要引入额外的dp数组，因此空间复杂度为 $O(N)$