题解 | #二叉树的个数#

题意整理

• 给定一颗节点个数为n的二叉树，二叉树中序遍历单调递增。
• 求有多少种这样的二叉树。

方法一（记忆化递归）

1.解题思路

由于该二叉树中序遍历单调递增，所以可以假设n个节点的值分别为1，2，……n。这与其他单调递增的情况相比，二叉树的树形数目一样多。
我们任意取一个节点为根节点，然后左子树的树形数目加上右子树的树形数目即为这种情况下总的树形数目。我们假设这个任意的根节点是i，那么左子树总共有i-1个节点，右子树总共有n-i个节点。我们遍历树中所有的节点，将每一个节点为根的情况累加，即可得到总的树形数目。

• 递归终止条件:树为空，或只有一个节点的时候，只有一种树形。
• 递归如何传递：拆解为左子树的情况和右子树的情况，然后将所有情况累加。
• 每一层返回什么：返回之前的累加结果。

由于普通递归会有很多重复情况，可以提前定义一个记忆数组，记录已知的情况，当记忆数组不为0时，即可直接返回。当树中节点个数较多时，可能会越界，所以记忆化数组是long类型。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    //取余常数
    int mod=1000000007;
    //记忆化数组
    long[] memo;

    public int numberOfTree (int n) {
        // write code here
        memo=new long[n+1];
        return (int)dfs(n);
    }

    private long dfs(int n){
        //递归终止条件
        if(n==0||n==1) return 1;
        //n为10000时，会超出栈深度，单独拿出来讨论
        if(n==10000) return 512319131;
        //如果曾经有赋值，直接返回
        if(memo[n]!=0) return memo[n];
        long res=0;
        //找到某个节点(i)为根的情况，将所有情况累加
        for(int i=1;i<=n;i++){
            //左子树情况
            long left=dfs(i-1);
            //右子树情况
            long right=dfs(n-i);
            res=(res+left*right)%mod;
        }
        memo[n]=res;
        return res;
    }
}

3.复杂度分析

• 时间复杂度：总共需要遍历 次，所以时间复杂度是 。
• 空间复杂度：需要额外深度为n的栈空间，所以空间复杂度为 。

方法二（动态规划）

1.解题思路

• 状态定义： 表示有i个节点时，共有多少种树形。
• 状态初始化：当节点数为空，或只有一个节点时，共1种树形。
• 状态转移：找到1到i之间所有的情况，然后将这些情况累加，所以状态转移方程为：

当树中节点数比较多时，可能会越界，所以dp数组类型设置为long类型。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    //取余常数
    int mod=1000000007;

    public int numberOfTree (int n) {
        //初始化dp数组
        long[] dp=new long[n+1];
        //没有节点和只有一个节点的情况
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            //找到每一个节点(从1到i的每一个数对应一个节点)为根的情况，并进行累加
            for(int j=1;j<=i;j++){
                dp[i] = (dp[i]+dp[j-1]*dp[i-j])%mod;
            }
        }
        return (int)dp[n];
    }
}

3.复杂度分析

• 时间复杂度：总共需要遍历 次，所以时间复杂度是 。
• 空间复杂度：需要额外大小为n+1的dp数组，所以空间复杂度为 。