首页 > 试题广场 >

小红的二叉树

[编程题]小红的二叉树

热度指数：6983 时间限制：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

输入

输出

说明

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

算法知识视频讲解

lhp_zml

发表于 2025-03-10 13:46:03

// 从深度为2开始，当前叶子节点为2个。每加一层，每个叶子节点会增加三条路径 #include<bits/stdc++.h> using namespace std; const int mod=1e9+7; int n; int main(){ cin>>n; 展开全文

此在Dasein

发表于 2026-02-10 00:25:45

中心节点枚举法在树（无环连通图）中，任意两个度数大于等于 2 的节点之间都存在路径。对于长度为 2 的路径，节点是该路径唯一的“中间节点”或“转折点”。因此，可以将“计算所有长度为 2 的路径数量”转化为：遍历树中每一个节点，计算以为中心（中点）能组成多少条路径。假设节点的度展开全文

Night_crusing

发表于 2026-02-10 12:49:15

最原始思路是对每一个节点进行判断然后累加，但是这样肯定会积累重复项。观察经过两个边的类型可以分为两种，子 - 父 - 子和孙 - 子 - 父两种，我们可以选择中间节点作为统计的口径。对于深度为2到n-1的中间的节点作为父节点可以得到一条（子 - 父 - 子）作为子节点可以获得两条（孙 - 子展开全文

CARLJOSEPHLEE

发表于 2025-03-10 22:49:02

n = int(input()) if n == 1: print(0) else: pow1 = pow(2,n-1,1000000007) print((3*pow1-5)%1000000007)

努力努力zzb

发表于 2025-04-04 21:10:28

shendu2 =input() shendu=int(shendu2) MOD=10**9+7 if shendu==1: print(0) else: ZHILI=pow(2,shendu-1,MOD) BABA=3*ZHILI-5 daan=BABA%MOD 展开全文

ading007

发表于 2025-05-23 14:30:17

package main import ( "fmt" ) const mod float64 = 1e9+7 func main() { var h int fmt.Scan(&h) cnt := 0 if h > 1 展开全文

牛客754921490号

发表于 2025-12-20 21:26:02

#include <iostream> #include <cmath> using namespace std; // 非根且非叶节点数量*3 + 有子节点的根节点 // 2^n n <=1e4 数字巨大，int明显越界，需要提前mod // (ab)%m = (a 展开全文

one_peace_Bo

发表于 2025-08-02 22:02:12

#include <cmath> #include <iostream> using namespace std; int main() { constexpr int MOD = 1e9+7; long long n; while (cin > 展开全文

我没拿98k

发表于 2025-04-03 16:23:50

n=int(input()) if n==1: print(0) else: print((3*2**(n-1)-5)%(10**9+7)) 数学问题(3*pow(2,n-1)) - 5

屁颠屁颠の父

发表于 2025-03-13 15:33:18

depth = int(input()) dp = [0] * depth dp[0] = 0 if depth == 1: print(dp[0]) elif depth == 2: dp[1] = 1 print(dp[1]) else: dp[1] = 1 展开全文

问题信息

数论

难度：

17条回答 40收藏 707浏览

小红的二叉树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题