平衡二叉树

题目描述

给定一棵含有 $N$ 个节点的平衡二叉树，求有多少种形态的平衡二叉树恰好有 $N$ 个节点。

平衡二叉树是一颗具有下列性质的二叉树：

1. 根结点的左右子树高度之差不超过 1
2. 每个子树也是构成平衡二叉树

由于答案可能比较大，输出总方案数模 $1,000,000,007$ 的余数。

输入格式

单个整数：表示 $N$

输出格式

单个整数：表示答案

数据范围

• 30% 的数据，$1\le N\le 10$
• 100% 的数据，$1\le N\le 5000$

样例数据

输入：

10

输出：

60

---

题解（仅添加注释，不修改代码）

解题思路

我采用动态规划解决本题：

1. 定义状态：dp[i][h] 表示i个节点、高度恰好为h的平衡二叉树的形态数量
2. 预处理：提前计算每个节点数对应的最小高度（完全二叉树）和最大高度（斐波那契树），缩小枚举范围
3. 状态转移：枚举根节点的左右子树节点数，保证左右子树高度差≤1，累加合法方案数
4. 答案统计：将n个节点所有合法高度的形态数求和，取模输出

完整注释代码

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;  // 取模常量
int n;                    // 输入的节点总数
long long dp[5005][20];   // dp[i][h]：i个节点、高度为h的平衡二叉树个数
int mh[5005];             // mh[i]：i个节点能构成的平衡二叉树最大高度
int minh[5005];           // minh[i]：i个节点能构成的平衡二叉树最小高度

// 预处理每个节点数的最大高度（斐波那契树：平衡二叉树最小节点数模型）
void init_max_height() {
    vector<int> S(25, 0);
    S[0] = 0;    // 高度0节点数为0
    S[1] = 1;    // 高度1节点数为1
    int max_h = 1;
    // 计算斐波那契树的最小节点数：S[h] = 左子树+右子树+根节点
    for (int h = 2; h < 25; h++) {
        S[h] = S[h-1] + S[h-2] + 1;
        if (S[h] <= n) max_h = h;
    }
    // 为每个节点数i赋值最大高度
    mh[0] = 0;
    int cur_h = 1;
    for (int i = 1; i <= n; i++) {
        // 找到当前节点数能达到的最大高度
        while (cur_h + 1 <= max_h && S[cur_h + 1] <= i) cur_h++;
        mh[i] = cur_h;
    }
}

// 预处理每个节点数的最小高度（完全二叉树：节点数最少的高度）
void init_min_height() {
    minh[0] = 0;
    int h = 1, max_nodes = 1; // 高度h的满二叉树最多有2^h-1个节点
    for (int i = 1; i <= n; i++) {
        // 节点数超过当前高度的满二叉树，高度+1
        if (i > max_nodes) {
            h++;
            max_nodes = (1 << h) - 1;
        }
        minh[i] = h;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    init_max_height();   // 预处理最大高度
    init_min_height();   // 预处理最小高度

    // DP边界初始化
    dp[0][0] = 1;  // 0个节点，高度0，1种形态
    dp[1][1] = 1;  // 1个节点，高度1，1种形态

    // 枚举总节点数i，从2开始递推
    for (int i = 2; i <= n; i++) {
        int z = i - 1;  // 根节点占1个，剩余z个节点分给左右子树
        // 枚举左子树节点数j，右子树节点数k=z-j
        for (int j = 0; j <= z; j++) {
            int k = z - j;

            // 枚举左子树所有合法高度
            int lh_low = minh[j], lh_high = mh[j];
            for (int hz = lh_low; hz <= lh_high; hz++) {
                if (dp[j][hz] == 0) continue;  // 无方案，跳过
                // 右子树高度必须满足：与左子树高度差≤1，且在自身合法高度范围内
                int rh_low = max(hz - 1, minh[k]);
                int rh_high = min(hz + 1, mh[k]);
                // 枚举右子树所有合法高度
                for (int hy = rh_low; hy <= rh_high; hy++) {
                    // 新树高度 = 左右子树最大高度 + 1
                    int new_h = max(hz, hy) + 1;
                    // 状态转移：累加左右子树的方案数乘积
                    dp[i][new_h] = (dp[i][new_h] + dp[j][hz] * dp[k][hy]) % MOD;
                }
            }
        }
    }

    // 统计n个节点所有高度的方案数总和
    long long ans = 0;
    for (int h = 1; h <= mh[n]; h++) {
        ans = (ans + dp[n][h]) % MOD;
    }
    cout << ans << '\n';

    return 0;
}

代码说明

1. 预处理高度：通过最小/最大高度预处理，大幅减少无效枚举，适配 $N\le 5000$ 的数据范围
2. 动态规划核心：利用子结构性质，将n个节点的问题分解为左右子树的子问题
3. 合法性约束：严格保证左右子树高度差不超过1，满足平衡二叉树定义
4. 取模处理：全程对 $10^9+7$ 取模，避免数值溢出并满足题目要求

---

总结

我用动态规划完美解决了这个问题，核心是状态定义+高度预处理+合法状态转移：

1. 用dp[i][h]记录i个节点、高度h的平衡二叉树数量
2. 预处理最小/最大高度，降低时间复杂度
3. 枚举左右子树节点数+高度，保证平衡二叉树性质，累加方案数
4. 最终求和所有合法高度的方案数，得到答案