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

SCAU--平衡树

news 来源：原创 2025/7/17 17:29:02

3 平衡树

Time Limit:1000MS Memory Limit:65535K

题型: 编程题语言: G++;GCC;VC;JAVA;PYTHON

描述

平衡树并不是平衡二叉排序树。
这里的平衡指的是左右子树的权值和差距尽可能的小。
给出n个结点二叉树的中序序列w[1],w[2],…,w[n]，请构造平衡树，并给出平衡树的先序序列。
平衡树构造算法如下：
（1）假设平衡树树根为序列中元素i，i左侧所有元素权值和S1=w[1]+w[2]+...+w[i-1],
其右侧所有元素权值和S2=w[i+1]+w[i+2]+...w[n]。在选择树根i时要求让S1-S2的绝对值最小。
例如5个元素序列 {5 4 1 2 3}，选择4为树根是最合适的，此时左侧权值和5，右侧权值和6，差值绝对值最小。
如选择其他结点为根，左右两侧权值和的差值绝对值会更大。
（2）选定树根i之后，对序列w[1],w[2],...,w[i-1]和w[i+1],w[i+2],...,w[n]分别构造平衡树，
作为树根i的左右子树。

5个元素序列 {5 4 1 2 3}的平衡树如上图，其先序序列为4 5 2 1 3。

输入格式

第一行一个整数n；
第二行n个正整数表示二叉树的中序序列。

输出格式

n个整数，平衡树的先序序列。
注意：如果选取树根时有两个结点，他们左右两侧权值和的差值绝对值相同，且均为最小值，
我们要求选择编号更小的结点。例如序列（7,6,2,9），选取6或2做树根时，两侧权值和的差值绝对值均为4，
此时要求选择6作为树根。

输入样例

4
7 6 2 9

输出样例

6 7 9 2

#include <iostream>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#include <string>
using namespace std;
typedef long long ll; // 定义long long类型别名llint n; // 节点数量
vector<ll> w; // 存储中序序列的权值，索引从1到n
vector<ll> p; // 前缀和数组，p[i]表示w[1]到w[i]的和
vector<int> pre; // 存储先序遍历结果的节点索引// 递归构建平衡树的函数
// 参数：
//   l: 当前子树在中序序列中的左边界
//   r: 当前子树在中序序列中的右边界
void build(int l, int r) {if (l > r) return; // 递归终止条件：左边界超过右边界ll minDiff = 10000000; // 初始化最小差值为一个大数int rootIndex = l; // 初始化根节点索引为左边界// 遍历当前子树的每个可能作为根节点的位置for (int i = l; i <= r; i++) {// 计算左子树的权值和：p[i-1] - p[l-1]ll leftSum = p[i - 1] - p[l - 1];// 计算右子树的权值和：p[r] - p[i]ll rightSum = p[r] - p[i];// 计算左右子树权值和的差的绝对值ll diff = abs(leftSum - rightSum);// 如果找到更小的差值，更新最小差值和根节点索引if (diff < minDiff) {minDiff = diff;rootIndex = i;}// 注意：题目要求当差值相同时选择编号较小的节点// 由于i是从左到右遍历的，所以自动满足这个条件}// 将当前根节点的索引加入先序序列pre.push_back(rootIndex);// 递归构建左子树build(l, rootIndex - 1);// 递归构建右子树build(rootIndex + 1, r);
}int main() {// 优化输入输出ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n; // 读取节点数量w.resize(n + 1); // 调整w的大小为n+1（索引1到n）p.resize(n + 1, 0); // 调整p的大小为n+1，并初始化为0// 读取权值并计算前缀和for (int i = 1; i <= n; i++) {cin >> w[i];p[i] = p[i - 1] + w[i]; // p[i] = w[1] + w[2] + ... + w[i]}// 从整个序列构建平衡树build(1, n);// 输出先序遍历结果（输出的是节点的权值，不是索引）for (int i = 0; i < pre.size(); i++) {cout << w[pre[i]] << ' ';}cout << endl;return 0;
}

SCAU--平衡树

3 平衡树 Time Limit:1000MS Memory Limit:65535K 题型: 编程题语言: G;GCC;VC;JAVA;PYTHON 描述平衡树并不是平衡二叉排序树。这里的平衡指的是左右子树的权值和差距尽可能的小。给出n个结点二叉树的中序序列w[1],w[2],…,w[n]，请构造平衡树&#xff0c…...

编程日记 2025/7/17 17:29:02

图的几种存储方法比较：二维矩阵、邻接表与链式前向星

图是一种非常重要的非线性数据结构，广泛应用于社交网络、路径规划、网络拓扑等领域。在计算机中表示和存储图结构有多种方法，本文将详细分析三种常见的存储方式：二维矩阵（邻接矩阵）、邻接表和链式前向星，比…...

编程日记 2025/7/17 4:55:49

【AS32X601驱动系列教程】MCU启动详解

在嵌入式开发领域，掌握MCU（微控制单元）的启动流程是工程师们迈向深入开发的关键一步。本文将带您深入了解MCU启动的奥秘，从编译过程到启动文件，再到链接脚本和系统时钟配置，全方位解析MCU启动流程。在实际…...

编程日记 2025/7/17 16:41:56

计算机视觉与深度学习｜ Matlab实现EMD-GWO-SVR、EMD-SVR、GWO-SVR、SVR时间序列预测（完整源码和数据）

以下是一个完整的Matlab时间序列预测实现方案，包含EMD-GWO-SVR、EMD-SVR、GWO-SVR和SVR四种方法的对比。代码包含数据生成、信号分解、优化算法和预测模型实现。 %% 主程序：时间序列预测对比实验 clc; clear; clearvars; close all;% 生成模拟时间序列数据 rng(1); % 固定随…...

编程日记 2025/7/17 16:45:31

Visual Studio 2022 插件推荐

Visual Studio 2022 插件推荐 Visual Studio 2022 (简称 VS2022) 是一款强大的 IDE，适合各类系统组件、框架和应用的开发。插件是接入 VS2022 最重要的扩展方式之一，它们可以大幅提升开发效率、优化代码质量，并提供强大的调试和分析功能。 …...

编程日记 2025/7/17 16:07:23

[luogu12541] [APIO2025] Hack! - 交互 - 构造 - 数论 - BSGS

传送门：https://www.luogu.com.cn/problem/P12541 题目大意：有一个数 n n n，你不知道是多少；你每次可以向交互库询问一个正整数集合 A A A（其中元素互不相同），交互库返回：将集合中…...

编程日记 2025/7/17 16:35:20

openjdk底层(hotspot)汇编指令调用（五）——内存访问

根据前面关于aarch64架构下的编码解释可知，在src\hotspot\cpu\架构文件夹下， assembler_xx.hpp assembler_xx.cpp register_xx.hpp register_xx.cpp register_definitions_xx.cpp这些文件是有关寄存器定义以及汇编编码函数实现的文件。对于前述的ope…...

编程日记 2025/7/17 16:02:50

几款常用的虚拟串口模拟器

几款常用的虚拟串口模拟器（Virtual Serial Port Emulator），适用于 Windows 系统，可用于开发和调试串口通信应用： 1. com0com (开源免费) 特点： 完全开源免费，无功能限制。可创建多个虚拟串口…...

编程日记 2025/7/17 1:22:44

ChimeraX介绍

UCSF ChimeraX 是一款由美国加州大学旧金山分校（UCSF）开发的下一代分子可视化软件，是经典的 UCSF Chimera 的继任者。它集成了强大的分子结构可视化、分析、建模和动画功能，广泛应用于结构生物学、药物设计、分子建模等领域。 1. 下载安装： Download UCSF ChimeraX 2. …...

编程日记 2025/7/17 1:08:28

【Linux】初见，基础指令

前言本文将讲解Linux中最基础的东西-----指令，带大家了解一下Linux中有哪些基础指令，分别有什么作用。本文中的指令和选项并不全，只介绍较为常用的 pwd指令语法：pwd 功能：显示当前所在位置（路径&#xf…...

编程日记 2025/7/17 16:21:05

链表的面试题8之环形链表

许久不见，那么这是最后倒数第三题了，这道题我们来看一下环形链表。老规矩贴链接：141. 环形链表 - 力扣（LeetCode） 目录倒数第k个元素获取中间元素的问题。双指针来，大致看一下题目，这…...

编程日记 2025/6/28 22:01:48

OBS Studio：windows免费开源的直播与录屏软件

OBS Studio是一款免费、开源且跨平台的直播与录屏软件。其支持 Windows、macOS 和 Linux。OBS适用于，有直播需求的人群或录屏需求的人群。 Stars 数64,323Forks 数8413 主要特点推流：OBS Studio 支持将视频实时推流至多个平台，如 YouTube、…...

编程日记 2025/6/28 22:01:55

邂逅Node.js

首先先要来学习一下nodejs的基础（和后端开发有联系的） 再然后的学习路线是学习npm，yarn，cnpm，npx，pnpm等包管理工具然后进行模块化的使用，再去学习webpack和git（版本控制工具&…...

编程日记 2025/7/17 17:18:14

React 常见的陷阱之（如异步访问事件对象）

文章目录前言1. 异步访问事件对象问题解决方案 2. 事件传播的误解**问题**解决方案 **3. 事件监听器未正确卸载****问题****解决方案** **4. 动态列表中的事件绑定****问题****解决方案** **5. 第三方库与 React 事件冲突****问题****解决方案** **6. 表单输入与受控组件****问…...

编程日记 2025/7/17 16:23:41

LinkedList demo 内部类讲说 1. Node节点2.MyLinkedList3. LinkedListTest 测试类 1. Node节点 public class Node<T> {private Node<T> pre;private Node<T> next;private T data;public Node() {}public Node getPre() {return pre;}public void setPre(N…...

编程日记 2025/7/16 21:43:27

Sql刷题日志（day9)

一、笔试 1、limit offset：分页查询 SELECT column1, column2, ... FROM table_name LIMIT number_of_rows OFFSET start_row; --跳过前 start_row 行，返回接下来的 number_of_rows 行。 2、lag、lead：查询前后行数据 --lag函数用于访问当…...

编程日记 2025/7/17 17:22:28

46 python pandas

Pandas是Python数据分析的利器，也是各种数据建模的标准工具一、什么是pandas pandas 是 Python 中用于数据处理和分析的核心库，提供了高效的数据结构（如Series和DataFrame）和数据操作工具，广泛应用于数据清洗、分析、可视化等场景。最常用的是用来处理excel数据。二…...

编程日记 2025/7/17 17:07:59

告别延迟！Ethernetip转modbustcp网关在熔炼车间监控的极速时代

熔炼车间热火朝天，巨大的热风炉发出隆隆的轰鸣声，我作为一名技术操控工，正密切关注着监控系统上跳动的各项参数。这套基于EtherNET/ip的监控系统，是我们车间数字化改造的核心，它将原本分散的控制单元整合在一起&#x…...

编程日记 2025/7/17 1:13:39

Prompt Tuning：高效微调大模型的新利器

Prompt Tuning（提示调优）是什么 Prompt Tuning（提示调优）是大模型参数高效微调（Parameter-Efficient Fine-Tuning, PEFT）的重要技术之一，其核心思想是通过优化连续的提示向量（而非整个模型参数）来适配特定任务。以下是关于 Prompt Tuning 的详细解析：一、核心概念…...

编程日记 2025/7/17 16:13:03

⼆叉搜索树详解

1. ⼆叉搜索树的概念⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树: • 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值 • 若它的右⼦树不为空，则右⼦树上所有结点的值都⼤于等于根结…...

编程日记 2025/7/9 5:04:35

CompleteableFuture的异步任务编排

为什么会有CompleteableFuture Java 的 1.5 版本引入了 Future，可以把它简单的理解为运算结果的占位符， 它提供了两个方法来获取运算结果。 get()：调用该方法线程将会无限期等待运算结果。get(longmeout, TimeUnit unit)：调用该…...

编程日记 2025/7/17 12:34:48

珈和科技贺李德仁院士荣膺国际数字地球学会会士：以时空智能赋能可持续发展目标绘就数字地球未来蓝图

4月22日，第十四届国际数字地球会议在重庆盛大启幕。在这场在全球范围内数字地球领域具有国际影响力的学术盛会上，国际数字地球学会向珈和科技的企业顾问，2023年度国家最高科学技术奖得主李德仁院士授予了“国际数字地球学会会士”最高荣誉称号…...

编程日记 2025/7/15 5:17:45

【CodeBuddy 】从0到1，打造一个“牛马打鸡血仪”

【CodeBuddy 】从0到1，打造一个“牛马打鸡血仪” 我正在参加CodeBuddy「首席试玩官」内容创作大赛，本文所使用的 CodeBuddy 免费下载链接：腾讯云代码助手 CodeBuddy - AI 时代的智能编程伙伴 🌟嗨，我是LucianaiB&#…...

编程日记 2025/7/11 8:19:07

BI是什么意思？一文讲清BI的概念与应用！

目录一、BI 是什么意思 1. BI 的定义 2. BI 的发展历程 3. BI 的核心组件二、BI 的应用场景 1. 销售与市场营销 2. 财务管理编辑3. 人力资源管理 4. 生产与运营管理编辑三、选择合适的 BI 工具 1. 考虑企业的需求和规模 2. 评估工具的功能和性能 3. 关注工…...

编程日记 2025/7/15 9:40:46

可编辑PPT | 华为安全架构设计方法指南华为数字化转型架构解决方案

这份文档是华为的安全架构设计方法指南，它详细介绍了安全架构设计的重要性、方法和流程。文档强调安全架构是软件研发技术体系中的关键DFX能力，与可靠性、性能等并列，尤其在云计算和复杂网络环境下，安全性设计显得尤为重要。华为的…...

编程日记 2025/7/16 9:17:25

1.6 提示词工程（二）

目录 3.2 提供参考文本 3.2.1 使用参考文本来构建答案 3.2.2 指导模型用引用的文本回答问题 3.3 把复杂的任务拆分成简单的子任务 3.3.1 利用意图分类确定与用户查询最相关的指令 3.3.2 针对需要长时间对话的应用程序，应概括或过滤之前的对话内容 …...

编程日记 2025/7/15 22:29:27

WIFI信号状态信息 CSI 深度学习之数据集

Building occupant activity sensing dataset based on WIFI CSI（WiSA） 所有的数据以及实验参数都上传到了figshare中并配备详细说明，供参考。论文链接：WiSA: Privacy-enhanced WiFi-based activity intensity recognition in …...

编程日记 2025/7/17 14:55:36

基于服务器的 DPI 深度分析解决方案

一、传统网络流量分析的瓶颈与挑战在企业网络管理体系中，传统流量分析模式高度依赖网络设备作为数据采集核心节点，无论是基于 NetFlow/IPFIX 等流协议的流量分析，还是通过端口镜像技术实现的流量监控，均以交换机、路由器等网络设…...

编程日记 2025/7/11 8:31:30

动态规划（5）：线性动态规划

引言所谓线性动态规划，通常指状态定义和转移具有线性结构的动态规划问题，其状态通常可以用一维数组表示，状态转移主要依赖于相邻或前面有限个状态。这类问题的特点是状态空间呈线性排列，每个状态只与有限个前置状态相关，使得问题结构相对简单，更容易理解和掌握。一维…...

编程日记 2025/7/14 14:55:12

c语言- 如何构建CMake项目（Linux/VSCode）

目录 linux（vscode）构建C语言CMake项目 1. 检查linux是否下载cmake，否则执行下列代码 2. 在vscode下载cmake的插件CMake Tools 3. 构建项目（项目结构） 4. 进行cmake配置 1. 在VS Code中按下ctrl shift p键&…...

编程日记 2025/7/17 7:17:50

HJ17 坐标移动【牛客网】

文章目录零、原题链接一、题目描述二、测试用例三、解题思路四、参考代码零、原题链接 HJ17 坐标移动一、题目描述二、测试用例三、解题思路基本思路： 这题的难点在于理解题目和如何处理各种情况。题目是给定一串指令，首先要判断指令是否合法…...

编程日记 2025/7/17 5:19:03

HGHAC集群滚动扩展或更换硬盘设备

文章目录环境文档用途详细信息环境系统平台：N/A 版本：4.5.8 文档用途集群版本：hghac4.2.1 数据库版本：hgdb-see-4.5.8 此步骤适用于所有hac架构的hgdb集群。主要用途：HAC集群服务器滚动扩展或更换硬盘本文…...

编程日记 2025/7/7 21:30:31

虚拟环境中VSCode运行jupyter文件

用VS Code打开jupyter文件，点击右上角 Select Kernel 在正上方会出现这个选择框，选择 Python Environment 会出来所有的虚拟环境，选择要用的环境行...

编程日记 2025/7/3 17:51:45

【蓝桥杯嵌入式】【模块】六、PWM相关配置及代码模板

1. 前言最近在准备16届的蓝桥杯嵌入式赛道的国赛，打算出一个系列的博客，记录STM32G431RBT6这块比赛用板上所有模块可能涉及到的所有考点，如果有错误或者遗漏欢迎各位大佬斧正。本系列博客会分为以下两大类： 1.1. 单独模块的讲…...

编程日记 2025/7/10 5:22:01

力扣-盛最多水的容器

1.题目描述 2.题目链接 11. 盛最多水的容器 - 力扣（LeetCode） 3.题目解析题目中的储水量两边差*短边高度。也就是说，两条边中，决定储水量的是短边的高度。我们可以定义两个指针，一个在最左边，一个在…...

编程日记 2025/7/15 17:28:49

数据实时同步：inotify + rsync 实现数据实时同步

1 数据实时同步在生产环境中，某些场景下，要将数据或文件进行实时同步，保证数据更新后其它节点能立即获得最新的数据。数据同步的两种方式 PULL：拉，使用定时任务的方式配合同步命令或脚本等，从指定服务…...

编程日记 2025/7/16 22:05:24

C#学习第24天：程序集和部署

程序集知识点 1.程序集的基本概念程序集是部署和版本控制的最小单位。它可以是可执行文件（.exe）或动态链接库（.dll）。包含元数据和清单（Manifest），描述程序集的内容和依赖关系。 2.程序集清单…...

编程日记 2025/7/10 14:13:36

mac .zshrc:1: command not found: 0 解决方案

nano ~/.zshrc 使用自带的nano命令打开文件，修改后 Ctrl X 然后输入y 然后回车即可保存成功一般情况下，不是常用这个命令，除非是遇到有问题的文件，才用， 例如遇到下面的问题 /Users/xxli/.zshrc:1: command no…...

编程日记 2025/7/11 12:55:22

学习设计模式《十》——代理模式

一、基础概念代理模式的本质【控制对象访问】； 代理模式的定义：为其他对象提供一种代理以控制对这个对象的访问； 代理模式的功能：代理模式是通过创建一个代理对象，用这个代理对象去代表真实的对象；客户端得…...

编程日记 2025/7/13 5:43:21

RestFul操作ElasticSearch：索引与文档全攻略

RestFul方式操作ES 索引库操作创建索引库 PUT /索引库名称 {"mappings":{"properties":{"字段名":{"type":"字段类型","analyzer":"分词器","index":"是否参与搜索(布尔值)"},…...

编程日记 2025/7/16 21:40:12

OpenCV 图像读取与显示

一、知识点: 1、读取图像 (1)、Mat imread( const String & filename, int flags IMREAD_COLOR_BGR ); (2)、返回值: Mat，返回读取的图像。若读取图像失败，则返回一个空的对象，对象.empty()为true。 (3)、参数filename: String是…...

编程日记 2025/7/13 22:22:46

Django快速入门篇

Django官网 https://docs.djangoproject.com/zh-hans/4.2/ 官方介绍官方版本推荐LTS版本，python3.9/3.10 djongo 每两年会出一个LTS版本关于环节djongo，conda直接安装即可 conda create -n myenv python3.9 conda activate myenv pip install dj…...

编程日记 2025/7/16 1:50:21

C++23 新增扁平化关联容器详解

文章目录一、引言已有关联容器回顾新容器的引入原因二、std::flat_set定义与特性代码示例适用场景三、std::flat_multiset定义与特性代码示例适用场景四、std::flat_map定义与特性代码示例适用场景五、std::flat_multimap定义与特性代码示例适用场景六、与其他容器的比较…...

编程日记 2025/7/15 10:07:18

当PLC遇上电焊机器人：EtherCAT转CANopen上演工业级“语言翻译官”

在汽车自动化产线中，PLC与电焊机器人的高效协同是提升生产效率的关键。但PLC常用的EtherCAT协议与电焊机器人采用的CANopen协议存在通信壁垒，JH-ECT009疆鸿智能EtherCAT转CANopen技术成为打破这一障碍的核心方案。应用拓扑图 EtherCAT是高速工业以太网协…...

编程日记 2025/7/3 14:40:25

LeetCode 1345. 跳跃游戏 IV（困难）

题目描述给你一个整数数组 arr ，你一开始在数组的第一个元素处（下标为 0）。每一步，你可以从下标 i 跳到下标 i 1 、i - 1 或者 j ： i 1 需满足：i 1 < arr.lengthi - 1 需满足：i - 1 …...

编程日记 2025/7/16 5:39:25

Linux bash shell的循环命令for、while和until

1、for命令 for命令，允许你创建一个遍历一系列值的循环，每次迭代都使用其中一个值来执行已定义好的一组命令。 for var in list do commands done # 在list参数中，你需要提供迭代中要用到的一系列值。 # 可以通过几种不同的方法指定列表中的…...

编程日记 2025/7/17 1:22:26

三、【数据建模篇】：用 Django Models 构建测试平台核心数据

【数据建模篇】：用 Django Models 构建测试平台核心数据前言我们要设计哪些核心数据？准备工作：创建 Django App开始设计数据模型 (Models)1. 通用基础模型 (可选但推荐)2. 项目模型 (Project)3. 模块模型 (Module)4. 测试用例模型 (TestCase…...

编程日记 2025/7/15 18:11:07