题解 | 小红的二叉树

// 从深度为2开始，当前叶子节点为2个。每加一层，每个叶子节点会增加三条路径
#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;
        for(int i=3;i<=n;i++){
            ans=(ans+yezi*3)%mod;
            yezi=(yezi*2)%mod;
        }
        cout<<ans%mod;
    }
    return 0;
}