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

华为OD机试 - 创建二叉树（Java 2024 E卷 200分）

news 2024/10/25 9:34:57

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+C卷）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

请按下列描述构建一颗二叉树 Q，并返回该树的根节点:

1、先创建值为 0 的根结点，根节点 Q 在第 0 层；
2、然后根据 operations 依次添加节点：operations[i] = [height, index] 表示对第 height 层的第 index 个节点 node，添加值为 i 的子节点：

若 node 无【左子节点】，则添加；
若 node 有【左子节点】但是没有【右子节点】，则添加右子节点；
若无可添加的子节点，则返回错误。

height, index 均为 0 开始计数； index 依存于节点的创建顺序。

注意：

输入用例保证每次操作对应的节点已存在；
控制台输出的内容是根据返回的树根节点，按层序遍历 Q 二叉树打印的结果。

二、输入描述

operations

三、输出描述

根据返回的树根节点，按照层序遍历 Q 二叉树打印的结果

备注

1 <= operations.length <= 100
operations[i].length == 2
0 <= operations[i][0] < 100
0 <= operations[i][1] < 100

四、测试用例

1、输入

[[0, 0], [0, 0], [1, 1], [1, 0], [0, 0]]

2、输出

[-1, 0, 1, 3, null, 2]

3、说明

首个值是根节点的值，也是返回值；
null 表示是空节点，此特殊层序遍历会遍历有值节点的 null 子节点

五、解题思路

1、问题分析

给定一系列操作，每个操作由两个整数 [height, index] 组成，表示在二叉树的第 height 层的第 index 个节点上添加一个子节点，子节点的值为操作的顺序索引 i。具体添加规则如下：

如果目标节点没有左子节点，则添加为左子节点。
如果目标节点已有左子节点但没有右子节点，则添加为右子节点。
如果目标节点的左右子节点都已存在，则返回错误（但题目保证输入操作都是有效的，可以添加节点）。

构建完二叉树后，进行层序遍历（广度优先遍历），并按照题目要求输出结果，空缺的节点用 null 表示。

2、具体步骤

初始化根节点：
- 创建根节点，值为 -1（根据测试用例）。
- 将根节点放入一个列表中，表示第0层。
构建树的层级结构：
- 使用一个二维列表 treeLevels，其中 treeLevels[h] 表示第 h 层的所有节点。
- 初始时，treeLevels[0] 只包含根节点。
处理每个操作：
- 遍历每个操作 [height, index]。
- 根据 height 和 index 找到目标父节点 parentNode。
- 创建一个新的子节点，值为当前操作的索引 i。
- 根据父节点的现有子节点情况，添加为左子节点或右子节点，并将新节点添加到 treeLevels[h + 1] 中对应层。
层序遍历：
- 使用队列进行广度优先遍历。
- 遍历过程中记录每个节点的值，如果节点为空，则记录 null。
- 最后移除结果列表末尾多余的 null 值。
输出结果：
- 将结果列表转换为字符串形式，按照题目要求的格式输出。

六、Java算法源码

public class OdTest {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 读取输入的操作字符串String inputLine = scanner.nextLine();// 解析输入字符串为二维整数数组Integer[][] operations = Arrays.stream(inputLine.substring(1, inputLine.length() - 1).split("(?<=]), (?=\\[)")).map(operationStr -> Arrays.stream(operationStr.substring(1, operationStr.length() - 1).split(", ")).map(Integer::parseInt).toArray(Integer[]::new)).toArray(Integer[][]::new);// 构建二叉树并输出结果System.out.println(buildBinaryTree(operations));}/*** 根据操作列表构建二叉树，并返回层序遍历结果的字符串表示。** @param operations 每个操作包含高度和索引，用于添加子节点* @return 层序遍历结果的字符串表示*/public static String buildBinaryTree(Integer[][] operations) {// 初始化根节点，值为 -1Node root = new Node(-1);// 存储每一层的节点列表，初始化第一层包含根节点List<Node> currentLevel = new ArrayList<>();currentLevel.add(root);// 存储所有层的节点，treeLevels.get(h) 获取第 h 层的节点列表List<List<Node>> treeLevels = new ArrayList<>();treeLevels.add(currentLevel);// 遍历每个操作，依次添加节点for (int i = 0; i < operations.length; i++) {int height = operations[i][0];int index = operations[i][1];// 如果当前树的层数不足以包含目标高度的下一层，则添加新的层if (treeLevels.size() <= height + 1) {treeLevels.add(new ArrayList<>());}// 创建新子节点，值为当前操作的索引 iNode childNode = new Node(i);// 获取目标父节点Node parentNode = treeLevels.get(height).get(index);// 如果父节点有空的子节点位置，则将新节点添加到下一层if (parentNode.leftChild == null || parentNode.rightChild == null) {treeLevels.get(height + 1).add(childNode);}// 将新节点分配为父节点的左子节点或右子节点if (parentNode.leftChild == null) {parentNode.leftChild = childNode;} else if (parentNode.rightChild == null) {parentNode.rightChild = childNode;}}// 进行层序遍历，记录节点值LinkedList<Integer> levelOrderValues = new LinkedList<>();LinkedList<Node> nodeQueue = new LinkedList<>();nodeQueue.add(treeLevels.get(0).get(0)); // 从根节点开始while (!nodeQueue.isEmpty()) {Node currentNode = nodeQueue.removeFirst();if (currentNode != null) {levelOrderValues.add(currentNode.value);nodeQueue.add(currentNode.leftChild);nodeQueue.add(currentNode.rightChild);} else {levelOrderValues.add(null);}}// 移除层序遍历结果末尾的多余 null 值while (!levelOrderValues.isEmpty() && levelOrderValues.getLast() == null) {levelOrderValues.removeLast();}// 将结果列表转换为字符串格式StringJoiner result = new StringJoiner(", ", "[", "]");for (Integer val : levelOrderValues) {result.add(val != null ? val.toString() : "null");}return result.toString();}
}/*** 定义二叉树的节点结构。*/
class Node {int value;Node leftChild;Node rightChild;public Node(int value) {this.value = value;this.leftChild = null;this.rightChild = null;}
}