• 2024年华为OD机试真题-生成哈夫曼树-Java-OD统一考试(C卷)


    题目描述:

    给定长度为n的无序的数字数组,每个数字代表二叉树的叶子节点的权值,数字数组的值均大于等于1。请完成一个函数,根据输入的数字数组,生成哈夫曼树,并将哈夫曼树按照中序遍历输出。

    为了保证输出的二叉树中序遍历结果统一,增加以下限制:二叉树节点中,左节点权值小于等于右节点权值,根节点权值为左右节点权值之和。当左右节点权值相同时,左子树高度高度小于等于右子树。

    注意:所有用例保证有效,并能生成哈夫曼树。

    提醒:哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。

    例如:

    由叶子节点5 15 40 30 10生成的最优二叉树如下图所示,该树的最短带权路径长度为40*1+30*2+15*3+5*4+10*4=205。

    输入描述:

    第一行输入为数组长度,记为N,1<=N<=1000,第二行输入无序数值数组,以空格分割,数值均大于等于1,小于100000

    输出描述:

    输出一个哈夫曼树的中序遍历的数组,数值间以空格分割

    补充说明:

    示例1

    输入:

    5
    5 15 40 30 10
    输出࿱

  • 相关阅读:
    项目开发混淆从初识到理解
    聊聊微前端沙箱
    八.Redis 主从复制
    Day23力扣打卡
    Machine Learning Model
    这个时代,让我们一起格局打开!【2022戴尔科技峰会预告】
    Julia编程基础
    JavaScript奇淫技巧:20行代码,实现屏幕录像
    (一)NIO 基础
    浅谈长连接负载均衡
  • 原文地址:https://blog.csdn.net/2301_76848549/article/details/136127883