华为OD机试真题 Java 实现【数组二叉树】【2023 B卷 200分】，附详细解题思路

目录

• • 专栏导读
  • 一、题目描述
  • 二、输入描述
  • 三、输出描述
  • 四、解题思路
  • 五、Java算法源码
  • 六、效果展示

专栏导读

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

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

二叉树也可以用数组来存储，给定一个数组，树的根节点的值存储在下标1，对于存储在下标N的节点，他的左子节点和右子节点分别存储在下标2N和2N+1，并且我们用值-1代表一个节点为空。

给定一个数组存储的二叉树，试求从根节点到最小的叶子节点的路径，路径由节点的值组成。

二、输入描述

输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割。

注意第一个元素即为根节点的值，即数组的第N个元素对应下标N,下标0在树的表示中没有使用，所以我们省略了。

输入的树最多为7层。

三、输出描述

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

四、解题思路

1. 输入一行为数组的内容，数组的每个元素都是正整数，元素间用空格分割；
2. 通过java8 Stream表达式（简洁/方便/上档次）快速拆解输入行；
3. 定义最小叶子节点的值min；
4. 定义最小叶子节点的索引minIndex；
5. 求解最小叶子节点的值和索引；
6. 定义集合pathList，存储最小叶子节点到根的路径；
7. 从最小叶子节点开始向上找父节点，直到树顶；
8. 输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分割；

五、Java算法源码

package com.guor.od;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
import java.util.StringJoiner;

public class OdTest {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        // 数组的内容，数组的每个元素都是正整数，元素间用空格分割
        Integer[] arr = Arrays.stream(sc.nextLine().split(" ")).map(Integer::parseInt).toArray(Integer[]::new);

        int n = arr.length - 1;

        // 最小叶子节点的值
        int min = Integer.MAX_VALUE;
        // 最小叶子节点的索引
        int minIndex = -1;

        // 求解最小叶子节点的值和索引
        for (int i = n; i >= 1; i--) {
            if (arr[i] != -1) {
                if (i * 2 + 1 <= n && arr[i * 2 + 1] != -1) {
                    continue;
                }
                if (i * 2 + 2 <= n && arr[i * 2 + 2] != -1) {
                    continue;
                }
                // 解最小叶子节点
                if (min > arr[i]) {
                    min = arr[i];
                    minIndex = i;
                }
            }
        }

        // 最小叶子节点到根的路径
        LinkedList<Integer> pathList = new LinkedList<>();
        pathList.addFirst(min);

        // 从最小叶子节点开始向上找父节点，直到树顶
        while (minIndex != 0) {
            int temp = (minIndex - 1) / 2;
            pathList.addFirst(arr[temp]);
            minIndex = temp;
        }

        // 输出从根节点到最小叶子节点的路径上，各个节点的值，由空格分割
        StringBuilder builder = new StringBuilder();
        for (int value :pathList) {
            builder.append(value).append(" ");
        }

        System.out.println(builder.substring(0,builder.length() - 1));
    }
}

六、效果展示

1、输入

3 5 7 -1 -1 2 4

2、输出

3 7 2

3、说明

最小叶子节点的路径为3 7 2

🏆下一篇：华为OD机试真题 Java 实现【路灯照明问题】【2022Q4 100分】，感谢fly晨发现这个问题，并提供更优质的算法

🏆本文收录于，华为OD机试（JAVA）真题（A卷+B卷）

刷的越多，抽中的概率越大，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。