题解 | 小红的二叉树

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int n;

int main(){
    cin >> n;

    // 特殊情况处理
    if(n == 1) {
        cout << 0;
    } else if(n == 2) {
        cout << 1;
    } else {
        // 初始化叶子节点数量和路径数量
        long long yezi = 2, ans = 1;

        // 从深度为 3 开始，逐层计算路径数量
        for(int i = 3; i <= n; i++) {
            // 每个叶子节点增加 3 条路径
            ans = (ans + yezi * 3) % mod;
            // 叶子节点数量翻倍
            yezi = (yezi * 2) % mod;
        }

        // 输出最终结果
        cout << ans % mod;
    }
    return 0;
}