深度优先搜索LeetCode979. 在二叉树中分配硬币
给你一个有 n 个结点的二叉树的根结点 root ,其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。
在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到子结点,或者从子结点移动到父结点。
返回使每个结点上 只有 一枚硬币所需的 最少 移动次数。

每个硬币移动一次就会经过一条边, 原问题可用转换为, 所有边被经过的次数之和。
二叉树中每一条边会连接一个子树,这个子树多的硬币会经过这条边,少的硬币会从其他地方运到该子树。
所以每个边被经过的次数,就是该边对应的子树中 节点个数 和 金币个数之差 的绝对值。
可以使用dfs来做。
vector<int>dfs(node *root):表示以root为根节点的树中 节点个数 和 金币个数 ,v[0]表示节点个数,v[1]表示金币个数。
vector<int>dfs(root):
vector<int>v,left,right;
if(root->left)
left = dfs (root->left);res += abs(left[0]-left[1]);
if(root->right)
right = dfs (root->right); res += abs(right[0]-right[1]);
v[0]=left[0]+right[0]+1;
v[1]=left[1]+right[1]+root->val;
return v;
class Solution {
public: int res=0;vector<int>dfs(TreeNode *root){vector<int>v(2,0);vector<int>left(2,0);vector<int>right(2,0); if(root->left){left = dfs(root->left);}if(root->right){right = dfs(root->right); }res += abs(left[0]-left[1]);res += abs(right[0]-right[1]);v[0]=left[0]+right[0]+1;v[1]=left[1]+right[1]+root->val;return v;}int distributeCoins(TreeNode* root) {dfs(root);return res;}
};
相关文章:
深度优先搜索LeetCode979. 在二叉树中分配硬币
给你一个有 n 个结点的二叉树的根结点 root ,其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。 在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到…...
C++学习之路(十)C++ 用Qt5实现一个工具箱(增加一个时间戳转换功能)- 示例代码拆分讲解
上篇文章,我们用 Qt5 实现了在小工具箱中添加了《JSON数据格式化》功能,还是比较实用的。为了继续丰富我们的工具箱,今天我们就再增加一个平时经常用到的功能吧,就是「 时间戳转换 」功能,而且实现点击按钮后文字进行变…...
Linux 5.15安全特性之ARM64 PAC
ARM64 PAC(Pointer Authentication Code)机制是ARM架构中引入的一种安全特性,旨在提供指针的完整性和安全性保护。它通过在指针中插入一段额外的代码进行签名,以验证指针的完整性,从而抵御缓冲区溢出和代码注入等攻击。…...
同旺科技 分布式数字温度传感器
内附链接 1、数字温度传感器 主要特性有: ● 支持PT100 / PT1000 两种铂电阻; ● 支持 2线 / 3线 / 4线 制接线方式; ● 支持5V~17V DC电源供电; ● 支持电源反接保护; ● 支持通讯波特率1200bps、2…...
状态空间的定义
状态空间是描述一个系统所有可能状态的集合。在系统理论、控制论、计算机科学、强化学习等领域,状态空间是一种常见的概念。 状态空间框架是一种用于描述和分析系统的方法,它包括系统的状态、状态之间的转移关系以及与状态相关的行为。下面详细解释状态…...
数据挖掘实战-基于word2vec的短文本情感分析
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...
大数据面试总结
1、冒泡排序、选择排序 2、二分查找 3、 hashmap和hashtable的区别?hashmap的底层实现原理? a、hashtable和hashmap的区别: 1、hashtable是线程安全的,会在每一个方法中都添加方法synchronize(同步机制)…...
利大于弊:物联网技术对电子商务渠道的影响
For Better or For Worse: Impacts of IoT Technology in e-Commerce Channel 物联网技术使用传感器和其他联网设备来手机和共享数据,并且被视为一种可以为供应链成员带来巨大的机会的突破性技术。本文的研究背景是:一个提供物联网基础设备的电子商务平…...
Python 元组详解(tuple)
文章目录 1 概述1.1 性质1.2 下标1.3 切片 2 常用方法2.1 访问:迭代、根据下标2.2 删除:del2.3 运算符:、*2.4 计算元组中元素个数:len()2.5 返回元组中元素最大值:max()2.6 返回元组中元素最小值:min()2.7…...
Redis部署-主从模式
目录 单点问题 主从模式 解析主从模式 配置redis主从模式 info replication命令查看复制相关的状态 断开复制关系 安全性 只读 传输延迟 拓扑结构 数据同步psync replicationid offset psync运行流程 全量复制流程 无硬盘模式 部分复制流程 积压缓冲区 实时复…...
全栈冲刺 之 一天速成MySQL
一、为什么使用数据库 数据储存在哪里? 硬盘、网盘、U盘、光盘、内存(临时存储) 数据持久化 使用文件来进行存储,数据库也是一种文件,像excel ,xml 这些都可以进行数据的存储,但大量数据操作…...
服务器运行train.py报错解决
在服务器配置完虚拟环境以及安装完各种所需库后,发现报错Traceback (most recent call last): File "/root/yolov5-master/yolov5-master/train.py", line 48, in <module> import val as validate # for end-of-epoch mAP File "/root/yolov5…...
Flutter开发type ‘Future<int>‘ is not a subtype of type ‘int‘ in type cast错误
文章目录 问题描述错误源码 问题分析解决方法修改后的代码 问题描述 今天有个同事调试flutter程序时报错,问我怎么解决,程序运行时报如下错误: type ‘Future’ is not a subtype of type ‘int’ in type cast 错误源码 int order Databas…...
Nginx(十二) gzip gzip_static sendfile directio aio 组合使用测试(2)
测试10:开启gzip、sendfile、aio、directio1m,关闭gzip_static,请求/index.js {"time_iso8601":"2023-11-30T17:20:5508:00","request_uri":"/index.js","status":"200","…...
hls实现播放m3u8视频将视频流进行切片 HLS.js简介
github官网GitHub - video-dev/hls.js: HLS.js is a JavaScript library that plays HLS in browsers with support for MSE.HLS.js is a JavaScript library that plays HLS in browsers with support for MSE. - GitHub - video-dev/hls.js: HLS.js is a JavaScript library …...
Ubuntu20.04部署TVM流程及编译优化模型示例
前言:记录自己安装TVM的流程,以及一个简单的利用TVM编译模型并执行的示例。 1,官网下载TVM源码 git clone --recursive https://github.com/apache/tvmgit submodule init git submodule update顺便完成准备工作,比如升级cmake版本…...
华为OD机试真题-两个字符串间的最短路径问题-2023年OD统一考试(C卷)
题目描述: 给定两个字符串,分别为字符串A与字符串B。例如A字符串为ABCABBA,B字符串为CBABAC可以得到下图m*n的二维数组,定义原点为(0, 0),终点为(m, n),水平与垂直的每一条边距离为1,映射成坐标系如下图。 从原点(0, 0)到(0, A)为水平边,距离为1,从(0, A)到(A, C)为垂…...
python try-except
相比于直接raise ValueError,使用try-except可以使程序在发生异常后仍然能够运行。 在try的部分中,当遇到第一个Error,就跳转到except中寻找对应类型的error,后续代码不再执行,如果try中有多个Error,注意顺…...
flutter开发实战-ValueListenableBuilder实现局部刷新功能
flutter开发实战-ValueListenableBuilder实现局部刷新功能 在创建的新工程中,点击按钮更新counter后,通过setState可以出发本类的build方法进行更新。当我们只需要更新一小部分控件的时候,通过setState就不太合适了,这就需要进行…...
通过时间交织技术扩展ADC采样速率的简要原理
前言 数据采集是将自然界中存在的模拟信号通过模数转换器(ADC)转换成数字信号,再对该数字信号进行相应的接收和处理。数据采集系统作为数据采集的手段,在移动通信、图向采集、无线电等领域有重要作用。随着电子信息技术的飞速发展…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
Ubuntu Cursor升级成v1.0
0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开,快捷键也不好用,当看到 Cursor 升级后,还是蛮高兴的 1. 下载 Cursor 下载地址:https://www.cursor.com/cn/downloads 点击下载 Linux (x64) ,…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
算法打卡第18天
从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder ,其中 inorder 是二叉树的中序遍历, postorder 是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。 示例 1: 输入:inorder [9,3,15,20,7…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
