首页 > 试题广场 >

小红的二叉树

[编程题]小红的二叉树

热度指数：5601 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 1024M，其他语言2048M
算法知识视频讲解

$\hspace{15pt}$ 小红想知道，深度为 $n$ 的满二叉树 $^{\texttt{[1]}}$ 有多少条长度为 $2$ 的简单路径 $^{\texttt{[2]}}$ ？由于答案可能很大，请将答案对 $(10^9+7)$ 取模后输出。
$\hspace{15pt}$ 在本题中，两条简单路径所包含的点集不同时，被视为不同的。例如，路径 $u-v$ 与路径 $v-u$ 被视为相同的，因为它们均包含点 $u$ 与点 $v$ 。

$\hspace{15pt}$ 一棵深度为 $h$ 的满二叉树 $^{\texttt{[1]}}$ 由恰好 $2^h-1$ 个节点组成，每一个节点要么是叶子节点，要么有 $2$ 个儿子，并且全部叶子节点的深度均为 $h$ 。
$\hspace{15pt}$ 简单路径 $^{\texttt{[2]}}$ 是指这样一条路径，其经过的顶点和边互不相同。

输入描述:

在一行上输入一个正整数  代表满二叉树的深度。

输出描述:

输出一个整数，代表深度为  的满二叉树中，长度为  的简单路径的数量。由于答案可能很大，请将答案对  取模后输出。

示例1

输入

输出

说明

在这个样例中，深度为  的满二叉树只有  个节点，所以没有长度为  的简单路径。

示例2

输入

输出

说明

在这个样例中，所给出的满二叉树如下图所示：

算法知识视频讲解

Java

牛客281381469号

考规律题，重要的是要知道当二叉树高度>= 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);
            }
        }
    }
}

发表于 2025-07-19 21:26:33 回复(0)

Java

Adhmor

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);
    }
}

为啥我没想到用BigInteger呢

发表于 2025-05-31 00:35:50 回复(0)

Java

牛客430757235号

//理解了还是挺简单的为啥没人提交awa 很难吗？？简易版

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);

// 注意 hasNext 和 hasNextLine 的区别

//有俩个问题一个是如何计算答案并通过string方式存储然后再以mod 取模方法取出答案输出

int n = in.nextInt();

if (n == 1) {

System.out.println(0);

return;

} else {

BigInteger a = new BigInteger("2");

BigInteger c = new BigInteger("6");

BigInteger e = new BigInteger("5");

BigInteger moshu = new BigInteger("1000000007");

BigInteger result = c.multiply(a.pow(n-2)).subtract(e).mod(moshu);

System.out.println(result);

}

发表于 2025-04-06 14:59:39 回复(0)

提交观点

问题信息

数论

难度：

5条回答 37收藏 441浏览

小红的二叉树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题