首页 > 试题广场 >

小红的二叉树

[编程题]小红的二叉树

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

输入

输出

说明

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

算法知识视频讲解

Python3

sailsweep

还是得简单罗列一下怎么计算简单路径的几个例子

深度 n=2：

树有 3 个节点：根节点 A，左叶子 B，右叶子 C。
路径数：只有一条路径 B−A−C（以 A 为中心）。
公式计算： 3⋅21−5=3⋅2−5=1，结果正确。

深度 n=3：

树有 7 个节点：根节点 A，第二层节点 B 和 C，第三层叶子节点 D、E、F、G。
路径数：以每个内部节点为中心：
- A（根）：路径 B−A−C，贡献 1。
- B（度数为 3）：路径 A−B−D、A−B−E、D−B−E，贡献 3。
- C（度数为 3）：路径 A−C−F、A−C−G、F−C−G，贡献 3。
总路径数： 1+3+3=7。
公式计算： 3⋅22−5=3⋅4−5=7，结果正确。

深度 n=4：

树有 15 个节点。
公式计算： 3⋅23−5=3⋅8−5=19。
验证：非叶子节点 7 个（根节点 1 个贡献 1，第 2 层节点 2 个各贡献 3，第 3 层节点 4 个各贡献 3），总路径数 1+2⋅3+4⋅3=19，正确。

发表于 2026-02-01 11:04:49 回复(0)

Python3

我的书出厂价格

h=int(input())

if h<2:

print(0)

else:

res=1+6*(2**(h-2)-1)%(10**9+7)

print(res)

啥啊这是

发表于 2025-04-09 09:44:11 回复(0)

提交观点

问题信息

数论

难度：

2条回答 39收藏 561浏览

小红的二叉树

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

问题信息

热门推荐

相关试题