栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

华为机试:数组二叉树,输出从根节点到最小叶子节点的路径上各个节点的值

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

华为机试:数组二叉树,输出从根节点到最小叶子节点的路径上各个节点的值

【编程题目 | 200分】数组二叉树 [ 200 / 中等 ]

题目描述

二叉树也可以用数组来存储,给定一个数组,树的根节点的值存储在下标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

思路分析
  • 首先找到最小叶子节点,没有子树的结点是叶子结点,-1不是节点。
  • 然后找到叶子节点到根节点的路径。
  • 最后输出。
代码参考

注:题目网上找的,参考代码是练习用,仅供参考,并不保证用例通过率。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;


public class Test11 {

    public static void main(String[] args) {
        // 读取输入的数字
        Scanner scanner = new Scanner(System.in);
        String[] s = scanner.nextLine().split(" ");
        int numSize = s.length;
        int[] nums = new int[numSize + 1];
        for (int i = 0; i < numSize; i++) {
            nums[i + 1] = Integer.parseInt(s[i]);
        }

        // 先找到最小叶子节点
        // 二叉树的叶子节点数:没有子树的结点是叶子结点
        int min = Integer.MAX_VALUE;
        int minPox = 0;
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            if (num == -1 || num > min) {
                continue;
            }
            if (2 * i > numSize) {
                min = num;
                minPox = i;
            } else {
                if (nums[2 * i] == -1 && nums[2 * i + 1] == -1) {
                    min = num;
                    minPox = i;
                }
            }
        }

        // 逆序从叶子节点找到根节点
        List paths = new ArrayList<>();
        int index = minPox;
        int yu = 0;
        while (index > 1) {
            paths.add(nums[index]);
            yu = index % 2;
            index = index / 2;
        }
        if (yu == 1) {
            paths.add(nums[1]);
        }

        // 输出根节点到最小的叶子节点的路径
        for (int i = paths.size() - 1; i >= 0; i--) {
            System.out.print(paths.get(i));
            if (i > 0) {
                System.out.print(" ");
            } else {
                System.out.println();
            }
        }
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/951122.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号