二叉树题解

链接：https://www.nowcoder.com/questionTerminal/aaefe5896cce4204b276e213e725f3ea?answerType=1&f=discussion

来源：牛客网

小强现在有𝑛个节点,他想请你帮他计算出有多少种不同的二叉树满足节点个数为

𝑛且树的高度不超过𝑚的方案.因为答案很大,所以答案需要模上1e9+7后输出.

树的高度: 定义为所有叶子到根路径上节点个数的最大值.

这个问题是一个典型的动态规划问题，要求计算在给定节点数 ( n ) 和高度限制 ( m ) 的条件下，可以构造出多少种不同的二叉树。由于答案可能非常大，需要对结果取模 ( 10^9 + 7 )。

问题分析

1. 定义状态：用 ( dp[i][j] ) 表示有 ( i ) 个节点且高度不超过 ( j ) 的二叉树的数量。
2. 状态转移方程：对于每个节点数 ( i )，高度限制 ( j )，考虑根节点的左子树和右子树的划分。假设左子树有 ( k ) 个节点，那么右子树就有 ( i - 1 - k ) 个节点。左子树和右子树的高度限制为 ( j - 1 )（因为根节点占用一层高度）。因此，状态转移方程为： [ dp[i][j] = \sum_{k=0}^{i-1} dp[k][j-1] \times dp[i-1-k][j-1] ]
3. 边界条件：( dp[0][j] = 1 )：空树的高度为 0，只有一种情况。( dp[i][0] = 0 )（对于 ( i > 0 )）：非空树的高度不能为 0。
4. 最终结果：( dp[n][m] ) 即为所求。

代码实现

以下是 Python 的实现代码：

mod = 1000000007

def count_trees(n, m):
    # 初始化 dp 数组
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 空树的情况
    for j in range(m + 1):
        dp[0][j] = 1
    
    # 动态规划填表
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            for k in range(i):
                dp[i][j] = (dp[i][j] + dp[k][j - 1] * dp[i - 1 - k][j - 1]) % mod
    
    return dp[n][m]

# 输入
n, m = map(int, input().split())
# 输出结果
print(count_trees(n, m))

代码解释

1. 初始化：dp[0][j] = 1：空树的高度为 0，只有一种情况。dp[i][0] = 0（对于 ( i > 0 )）：非空树的高度不能为 0。
2. 动态规划填表：外层循环遍历节点数 ( i )。中层循环遍历高度限制 ( j )。内层循环遍历左子树的节点数 ( k )，计算右子树的节点数 ( i - 1 - k )。根据状态转移方程更新 ( dp[i][j] )。
3. 取模操作：每次计算结果时对 ( 10^9 + 7 ) 取模，防止结果溢出。

示例

对于输入 ( n = 3 )，( m = 3 )，程序输出为 5，符合题目中的示例。

时间复杂度

• 时间复杂度为 ( O(n \times m \times n) = O(n^2 \times m) )。
• 空间复杂度为 ( O(n \times m) )。

这个解法能够高效地解决题目要求的问题。