华为OD机试 - 创建二叉树(Java 2024 E卷 200分)
华为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;}
}
七、效果展示
1、输入
[[0, 0], [1, 0], [1, 0], [2, 1], [2, 1], [2, 1], [2, 0], [3, 1], [2, 0]]
2、输出
[-1, 0, null, 1, 2, 6, 8, 3, 4, null, null, null, null, null, null, 7]
3、说明
首个值是根节点的值,也是返回值;
null 表示是空节点,此特殊层序遍历会遍历有值节点的 null 子节点
🏆下一篇:华为OD机试 - 简易内存池 - 逻辑分析(Java 2024 E卷 200分)
🏆本文收录于,华为OD机试(JAVA)真题(E卷+D卷+A卷+B卷+C卷)
刷的越多,抽中的概率越大,私信哪吒,备注华为OD,加入华为OD刷题交流群,每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景,发现新题目,随时更新,全天CSDN在线答疑。