华为OD机试真题---数组二叉树
华为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，则更新idx
if (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机试中，性能优化通常不是主要考察点，但良好的编程习惯和性能意识仍然是很重要的。
综上所述，华为OD机试中的“数组二叉树”题目主要考察了对数组与二叉树对应关系的理解、二叉树的遍历以及特定功能的实现。通过理解题目要求、掌握解题思路并编写正确的代码，可以成功解决这类问题。
原文地址：https://blog.csdn.net/lbp0123456/article/details/143730774
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！