【华为OD-E卷 - 数组二叉树 100分（python、java、c++、js、c）】
题目
二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，它的左子节点和右子节点分别存储在下标2N和2N+1，并且我们用值-1代表一个节点为空。
给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成
输入描述
- 输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分隔。
注意第一个元素即为根节点的值，即数组的第N个元素对应下标N，下标0在树的表示中没有使用，所以我们省略了。
输入的树最多为7层
输出描述
- 输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分隔，用例保证最小叶子节点只有一个
用例
用例一：
输入：
3 5 7 -1 -1 2 4
- 1
输出：
3 7 2
- 1
用例二：
输入：
5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6
- 1
输出：
5 8 7 6
- 1
python解法
- 解题思路：
- 问题描述：
给定一个以数组形式表示的完全二叉树，数组的第 i 个元素表示树中某个节点的值，值为 -1 表示节点为空。
找出所有叶子节点中值最小的那个，然后输出从根节点到该叶子节点的路径。
二叉树特性：
节点的左子节点索引为 2 * i + 1。
节点的右子节点索引为 2 * i + 2。
根节点索引为 0。
解题步骤：
找到所有叶子节点：
叶子节点定义：没有子节点的节点。
判断条件：
节点的值不为 -1。
它的左右子节点要么不存在（索引超出范围），要么值为 -1。
找到值最小的叶子节点：
遍历所有叶子节点，找出值最小的那个节点的索引。
构建从根节点到该叶子节点的路径：
从叶子节点开始，不断回溯到其父节点，最终到达根节点。
父节点索引为 (i - 1) // 2。
时间复杂度：
找到所有叶子节点：O(n)，遍历一次数组。
找到值最小的叶子节点：O(n)，比较所有叶子节点的值。
构建路径：O(log n)，最多回溯树的高度。
总复杂度：O(n)。
def get_pth(a):
"""
找出完全二叉树中值最小的叶子节点，并返回从根节点到该叶子节点的路径。
:param a: 完全二叉树的数组表示
:return: 根节点到值最小叶子节点的路径字符串
"""
n = len(a) - 1 # 数组的最后一个索引
# 找出所有叶子节点的索引
lvs = [
i for i in range(n, 0, -1) # 从后往前遍历节点
if a[i] != -1 and # 节点值不为 -1
((i * 2 + 1 > n or a[i * 2 + 1] == -1) and # 左子节点不存在或为空
(i * 2 + 2 > n or a[i * 2 + 2] == -1)) # 右子节点不存在或为空
]
# 找到值最小的叶子节点的索引
mn_lf = min(lvs, key=lambda i: a[i])
def bld_pth(idx):
"""
构建从根节点到指定索引节点的路径
:param idx: 当前节点索引
:return: 从根到该节点的路径数组
"""
if idx == 0: # 根节点
return [a[idx]]
return bld_pth((idx - 1) // 2) + [a[idx]] # 回溯到父节点
# 返回路径，转换为字符串形式
return " ".join(map(str, bld_pth(mn_lf)))
# 输入并调用函数
a = list(map(int, input().split())) # 输入二叉树数组
print(get_pth(a)) # 输出路径
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
java解法
- 解题思路
- 问题描述：
给定一个以数组形式表示的完全二叉树（从索引 1 开始表示节点，-1 表示空节点），找到所有叶子节点中值最小的叶子节点。
输出从根节点到该叶子节点的路径。
树的索引特性：
当前节点索引为 idx：
左子节点索引为 2 * idx。
右子节点索引为 2 * idx + 1。
根节点索引为 1。
如果索引超出数组范围，或者节点值为 -1，表示该节点为空。
实现方法：
使用递归深度优先搜索（DFS）遍历二叉树。
在递归过程中：
构建当前节点的路径。
如果是叶子节点（无左右子节点）：
判断该节点是否是值最小的叶子节点。
如果是，更新结果路径。
如果不是叶子节点，继续递归其左右子节点。
递归结束后，返回存储的路径。
关键逻辑：
叶子节点判断：
当前节点的左右子节点不存在或为空时，认为是叶子节点。
路径更新：
使用 List 存储当前路径。
使用 List 存储结果路径。
最小值记录：
使用数组 minVal[0] 存储当前最小叶子节点的值。
时间复杂度：
遍历整个树，复杂度为 O(n)，其中 n 是节点数
import java.util.*;
public class Main {
public static void main(String[] args) {
// 读取输入并解析为数组形式的完全二叉树
Scanner sc = new Scanner(System.in);
int[] tr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
// 存储结果路径
List<Integer> res = new ArrayList<>();
// 调用递归函数找到值最小叶子节点的路径
findMinLeafPath(tr, 1, res, new ArrayList<>(), new int[]{Integer.MAX_VALUE});
// 输出路径
System.out.println(String.join(" ", res.stream().map(String::valueOf).toArray(String[]::new)));
}
/**
* 递归查找从根到值最小叶子节点的路径
*
* @param tr 完全二叉树的数组表示
* @param idx 当前节点的索引（从 1 开始）
* @param res 存储结果路径
* @param curPath 存储当前路径
* @param minVal 存储当前最小叶子节点的值
*/
private static void findMinLeafPath(int[] tr, int idx, List<Integer> res, List<Integer> curPath, int[] minVal) {
// 如果索引超出范围或节点值为 -1，直接返回
if (idx >= tr.length || tr[idx - 1] == -1) {
return;
}
// 将当前节点值添加到当前路径
curPath.add(tr[idx - 1]);
// 判断是否是叶子节点
if (2 * idx >= tr.length || // 没有左子节点
(tr[2 * idx - 1] == -1 && // 左子节点为空
(2 * idx + 1 >= tr.length || tr[2 * idx] == -1))) { // 右子节点为空或不存在
// 如果当前叶子节点值小于当前最小值，更新最小值和结果路径
if (tr[idx - 1] < minVal[0]) {
minVal[0] = tr[idx - 1]; // 更新最小值
res.clear(); // 清空结果路径
res.addAll(new ArrayList<>(curPath)); // 更新结果路径
}
} else {
// 如果不是叶子节点，递归遍历左子节点和右子节点
findMinLeafPath(tr, 2 * idx, res, curPath, minVal); // 左子节点
findMinLeafPath(tr, 2 * idx + 1, res, curPath, minVal); // 右子节点
}
// 当前节点遍历完成后，从当前路径中移除
curPath.remove(curPath.size() - 1);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
C++解法
- 解题思路
更新中
- 1
C解法
更新中
- 1
JS解法
输入一个以数组形式表示的完全二叉树，其中 -1 表示空节点。
找出所有叶子节点中值最小的节点，并输出从根节点到该叶子节点的路径。
二叉树数组表示：
对于当前节点索引 index：
左子节点索引为 2 * index + 1。
右子节点索引为 2 * index + 2。
根节点索引为 0。
算法实现：
广度优先搜索 (BFS)：
使用队列来遍历树，记录每个节点的索引和从根到该节点的路径。
每次从队列中取出一个节点：
如果是叶子节点（左右子节点不存在或为空），检查是否是当前最小叶子节点。
如果不是叶子节点，继续将其左右子节点加入队列。
路径记录：
每个节点在队列中记录其索引和从根到当前节点的路径。
更新最小叶子节点时，保存其路径。
时间复杂度：
遍历数组一次：O(n)。
总时间复杂度：O(n)
const readline = require("readline");
// 创建读取输入的接口
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
// 每当读取到一行输入时执行
rl.on("line", (line) => {
const arr = line.split(" ").map(Number); // 解析输入为数组
let min = Infinity; // 初始化最小叶子节点值为无穷大
let path = []; // 用于存储最小叶子节点的路径
let queue = [{ index: 0, currentPath: [arr[0]] }]; // 队列初始化，存储根节点信息
// 广度优先搜索（BFS）遍历树
while (queue.length > 0) {
// 取出队列中的第一个节点
const { index, currentPath } = queue.shift();
// 如果当前节点索引超出范围或是空节点，跳过
if (index >= arr.length || arr[index] === -1) continue;
// 计算左子节点和右子节点的索引
const left = 2 * index + 1;
const right = 2 * index + 2;
// 判断是否为叶子节点（没有左右子节点或左右子节点为空）
if (left >= arr.length || arr[left] === -1) {
if (right >= arr.length || arr[right] === -1) {
// 如果是叶子节点，更新最小值和路径
if (arr[index] < min) {
min = arr[index];
path = currentPath;
}
}
}
// 将左子节点加入队列
if (left < arr.length) {
queue.push({ index: left, currentPath: [...currentPath, arr[left]] });
}
// 将右子节点加入队列
if (right < arr.length) {
queue.push({ index: right, currentPath: [...currentPath, arr[right]] });
}
}
// 输出最小叶子节点的路径
console.log(path.join(" "));
});
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
注意：
如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏
评论记录：
回复评论：