小红的二叉树

n=int(input())
if n==1:
    print(0)
else:
    print((3*2**(n-1)-5)%(10**9+7))

考规律题，重要的是要知道当二叉树高度>= 2时，路径总数s = 3 * pow(2 * 1.0, (n - 1) * 1.0) - 5。另外为防止数值溢出，收集i结果变量需要定为long型，且需要在每一次乘法后 % 1000000007，最后输出答案即可。
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        final long mod = 1000000007;
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            if (n == 1){
                System.out.println(0);
            } else{
                long res = 1;
                for (int i = 0; i < n - 1; i++){
                    res *= 2;
                    res %= mod;
                }
                long s  = (3 * res) % mod - 5;
                System.out.println(s);
            }
        }
    }
} 

import java.util.Scanner; 
import java.math.BigInteger;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        BigInteger out = func(n);
        BigInteger seven = new BigInteger("7");
        BigInteger ten = new BigInteger("10");
        System.out.println(out.remainder(ten.pow(9).add(seven)));
    }

    private static BigInteger func(int level){
        if(level == 1) {
            return new BigInteger("0");
        } else if (level == 2) {
            return new BigInteger("1");
        } else {
            BigInteger two = new BigInteger("2");
            BigInteger three = new BigInteger("3");
            return three.multiply(two.pow(level-2)).add(func(level-1));
        }
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        // ((2^n - 1) * 3 -2 ) mod 100000007
        int base = 1000000007;
        long baseRemainder = (1 << 30) % base;
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int deep = Integer.parseInt(bufferedReader.readLine()) - 1;
        int len = deep / 30;
        int less = deep % 30;
        long remainder = 1;
        for (int i = 0; i < len; i++) {
            remainder = (remainder * baseRemainder) % base;
        }
        remainder = remainder * ((1L << less) % base);
        remainder = (remainder - 1) * 3 % base;
        System.out.println(remainder > 0 ? remainder - 2 : remainder);
    }
}

 在这张图中，可以看出每次存在一个非页节点，就会有一条路径，每次存在一个高度为3的非叶子节点，就会有四条路径
故高度为3，可以计算出4+3*1种路径
#include <iostream>
using namespace std;

const int mod = 1e9+7;

unsigned long long Mypow(unsigned long long n, int m) {
    // 使用 unsigned long long 防止溢出
    for (int i = 1; i < m; ++i) {   // 执行 m-1 次左移
        n <<= 1;
        n %= mod;//每次移位都%一次，避免越界
    }
    return n;
}



int main() {
    int h;
    cin >> h;
    unsigned long long ans = 0;
    if (h > 1) {
        ans += (Mypow(2, h-1) - 1)%mod;  // 计算非叶子节点的贡献
    }
    if (h > 2) {
        ans += 4 * (Mypow(2, h-2) - 1)%mod;  // 计算高度为 2 节点的贡献
    }
    cout << ans % mod;  // 使用明确的模数
    return 0;
}

import java.math.BigInteger;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        if (n == 1)
            System.out.println(0);
        else if (n == 2)
            System.out.println(1);
        else {
            // 计算：3 * pow(2, n-1) - 5
            BigInteger A = BigInteger.ONE.shiftLeft(n - 1)
                    .multiply(BigInteger.valueOf(3))
                    .subtract(BigInteger.valueOf(5));

            // 计算：pow(10, 9) + 7
            BigInteger B = BigInteger.TEN.pow(9)
                    .add(BigInteger.valueOf(7));

            System.out.println(A.mod(B));
        }
    }

}