当前位置：首页 > news >正文

华为OD机试真题---数组二叉树

news 2024/11/14 11:56:05

华为OD机试中的“数组二叉树”题目通常涉及使用数组来表示二叉树，并进行相关的操作。以下是对这类题目的详细解析：

一、题目描述

二叉树只也可以用数组来存储，给定一个数组，树的根节点的值储存在下标1，对于储存在下标n的节点，他的左子节点和右子节点分别储存在下标2n和2n+1，并且我们用-1代表一个节点为空，给定一个数组存储的二叉树，试求从根节点到最小的叶子节点只的路径，路径由节点的值组成。

二、输入描述

输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割，注意第一个元素即为根节点的值，即数组的第n元素对应下标n，下标0在树的表示中没有使用，所以我们省略了，输入的树最多为7层。

三、输出描述

输出从根节点到最小叶子节点的路径上各个节点的值，由空格分割，用例保证最小叶子节点只有一个。

示例 1

输入:

3 5 7 -1 -1 2 4

输出:

3 7 2

示例 2
输入:

5 9 8 -1 -1 7 -1 -1 -1 -1 -1 6

输出:

5 8 7 6

四、解题思路

理解数组与二叉树的对应关系：
- 数组的第一个元素（下标0）通常不使用，根节点存储在数组的下标1位置。
- 对于数组中的任意节点N，其左子节点存储在2N位置，右子节点存储在2N+1位置。
- 使用-1表示空节点。
遍历数组构建二叉树（如果需要）：
- 可以使用递归或迭代的方式，根据数组中的值构建出对应的二叉树结构。
- 需要注意空节点的处理，即数组值为-1的情况。
实现特定功能：
- 根据题目要求，实现找到从根节点到最小叶子节点的路径等功能。
- 这通常涉及遍历二叉树（如深度优先搜索或广度优先搜索），并记录相关信息（如最小叶子节点的路径）。

五、代码实现

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;public class ArrayBinaryTree {/*** 主函数，用于处理输入的字符串，将其转换为整数数组，并根据特定的规则找到并打印出结果序列*/public static void main(String[] args) {try (Scanner sc = new Scanner(System.in)) {// 读取一行输入，并将其按空格分割为字符串数组String[] strings = sc.nextLine().split(" ");int len = strings.length;// 如果输入为空，则打印提示信息并退出if (len == 0) {System.out.println("No input provided.");return;}// 初始化一个整数数组，用于存储输入的数字int[] ints = new int[len];// 遍历字符串数组，将其转换为整数数组for (int i = 0; i < len; i++) {try {ints[i] = Integer.parseInt(strings[i]);} catch (NumberFormatException e) {// 如果转换失败，则打印错误信息并退出System.err.println("Invalid input: " + strings[i]);return;}}// 初始化一个索引变量，用于记录满足条件的最小元素的索引int idx = -1;// 遍历整数数组，寻找满足条件的元素for (int i = 0; i < len; i++) {if (ints[i] == -1) {continue;}int leftChild = (i + 1) * 2 - 1;int rightChild = (i + 1) * 2;// 如果当前元素的左子节点或右子节点超出数组范围，或者子节点都为-1，则更新idxif (leftChild >= len || (ints[leftChild] == -1 && ints[rightChild] == -1)) {if (idx == -1 || ints[idx] > ints[i]) {idx = i;}}}// 使用栈来存储从根节点到满足条件的元素的路径Deque<Integer> stack = new ArrayDeque<>();stack.push(idx);// 回溯找到满足条件的元素的路径while (idx > 0) {idx = (idx - 1) / 2;stack.push(idx);}// 构建结果字符串String ret = "";while (!stack.isEmpty()) {ret += " " + ints[stack.pop()];}// 打印结果字符串System.out.println(ret.substring(1));}}}

六、实例解析

1. 输入读取与转换

首先，程序读取一行输入并将其按空格分割成字符串数组：

String[] strings = sc.nextLine().split(" ");

对于输入 3 5 7 -1 -1 2 4，分割后的字符串数组为：

strings = ["3", "5", "7", "-1", "-1", "2", "4"]

然后，将字符串数组转换为整数数组：

int[] ints = new int[len];
for (int i = 0; i < len; i++) {ints[i] = Integer.parseInt(strings[i]);
}

转换后的整数数组为：

ints = [3, 5, 7, -1, -1, 2, 4]

2. 寻找满足条件的元素

接着，程序遍历整数数组，寻找满足条件的元素。条件是当前元素的左子节点或右子节点超出数组范围，或者子节点都为 -1。

对于数组 ints，我们计算每个元素的左右子节点索引：

对于 ints[0] = 3：左子节点 1，右子节点 2（都有效）
对于 ints[1] = 5：左子节点 3，右子节点 4（都有效）
对于 ints[2] = 7：左子节点 5（有效），右子节点 6（有效）
对于 ints[3] = -1：跳过
对于 ints[4] = -1：跳过
对于 ints[5] = 2：左子节点 11（超出范围），右子节点 12（超出范围）
对于 ints[6] = 4：左子节点 13（超出范围），右子节点 14（超出范围）

因此，ints[5] = 2 和 ints[6] = 4 都满足条件，但我们需要找到满足条件的最小元素。所以，比较 2 和 4，2 更小，所以 idx = 5。

3. 回溯路径

使用栈来存储从根节点到满足条件的元素的路径：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(idx);  // stack = [5]

然后回溯找到满足条件的元素的路径：

while (idx > 0) {idx = (idx - 1) / 2;stack.push(idx);
}

回溯过程如下：

idx = 5，父节点索引 (5 - 1) / 2 = 2，stack = [5, 2]
idx = 2，父节点索引 (2 - 1) / 2 = 1，stack = [5, 2, 1]
idx = 1，父节点索引 (1 - 1) / 2 = 0，stack = [5, 2, 1, 0]

4. 构建结果字符串并打印

最后，从栈中弹出元素构建结果字符串并打印：

String ret = "";
while (!stack.isEmpty()) {ret += " " + ints[stack.pop()];
}
System.out.println(ret.substring(1));

栈弹出顺序为 [0, 1, 2, 5]，对应值为 [3, 5, 7, 2]，所以结果字符串为 "3 5 7 2"。

因此

输入：3 5 7 -1 -1 2 4

输出：3 5 7 2

这表示从根节点到满足条件的元素 2 的路径上的元素依次为 3, 5, 7, 2。

七、注意事项

输入输出格式：
- 注意题目要求的输入输出格式，确保程序能够正确读取输入并输出符合要求的结果。
- 在华为OD机试中，通常需要使用Scanner类来读取输入，并使用System.out.println来输出结果。
边界条件：
- 注意处理边界条件，如空数组、只有一个节点的数组等。
- 确保程序在各种情况下都能正确运行并输出结果。
性能优化：
- 如果题目对性能有要求，可以尝试优化算法，如使用更高效的数据结构或算法来减少时间复杂度。
- 在华为OD机试中，性能优化通常不是主要考察点，但良好的编程习惯和性能意识仍然是很重要的。