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

深度优先搜索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 &#xff0c;其中树中每个结点 node 都对应有 node.val 枚硬币。整棵树上一共有 n 枚硬币。 在一次移动中&#xff0c;我们可以选择两个相邻的结点&#xff0c;然后将一枚硬币从其中一个结点移动到另一个结点。移动可以是从父结点到…...

C++学习之路(十)C++ 用Qt5实现一个工具箱(增加一个时间戳转换功能)- 示例代码拆分讲解

上篇文章&#xff0c;我们用 Qt5 实现了在小工具箱中添加了《JSON数据格式化》功能&#xff0c;还是比较实用的。为了继续丰富我们的工具箱&#xff0c;今天我们就再增加一个平时经常用到的功能吧&#xff0c;就是「 时间戳转换 」功能&#xff0c;而且实现点击按钮后文字进行变…...

Linux 5.15安全特性之ARM64 PAC

ARM64 PAC&#xff08;Pointer Authentication Code&#xff09;机制是ARM架构中引入的一种安全特性&#xff0c;旨在提供指针的完整性和安全性保护。它通过在指针中插入一段额外的代码进行签名&#xff0c;以验证指针的完整性&#xff0c;从而抵御缓冲区溢出和代码注入等攻击。…...

同旺科技 分布式数字温度传感器

内附链接 1、数字温度传感器 主要特性有&#xff1a; ● 支持PT100 / PT1000 两种铂电阻&#xff1b; ● 支持 2线 / 3线 / 4线 制接线方式&#xff1b; ● 支持5V&#xff5e;17V DC电源供电&#xff1b; ● 支持电源反接保护&#xff1b; ● 支持通讯波特率1200bps、2…...

状态空间的定义

状态空间是描述一个系统所有可能状态的集合。在系统理论、控制论、计算机科学、强化学习等领域&#xff0c;状态空间是一种常见的概念。 状态空间框架是一种用于描述和分析系统的方法&#xff0c;它包括系统的状态、状态之间的转移关系以及与状态相关的行为。下面详细解释状态…...

数据挖掘实战-基于word2vec的短文本情感分析

&#x1f935;‍♂️ 个人主页&#xff1a;艾派森的个人主页 ✍&#x1f3fb;作者简介&#xff1a;Python学习者 &#x1f40b; 希望大家多多支持&#xff0c;我们一起进步&#xff01;&#x1f604; 如果文章对你有帮助的话&#xff0c; 欢迎评论 &#x1f4ac;点赞&#x1f4…...

大数据面试总结

1、冒泡排序、选择排序 2、二分查找 3、 hashmap和hashtable的区别&#xff1f;hashmap的底层实现原理&#xff1f; a、hashtable和hashmap的区别&#xff1a; 1、hashtable是线程安全的&#xff0c;会在每一个方法中都添加方法synchronize&#xff08;同步机制&#xff09…...

利大于弊:物联网技术对电子商务渠道的影响

For Better or For Worse: Impacts of IoT Technology in e-Commerce Channel 物联网技术使用传感器和其他联网设备来手机和共享数据&#xff0c;并且被视为一种可以为供应链成员带来巨大的机会的突破性技术。本文的研究背景是&#xff1a;一个提供物联网基础设备的电子商务平…...

Python 元组详解(tuple)

文章目录 1 概述1.1 性质1.2 下标1.3 切片 2 常用方法2.1 访问&#xff1a;迭代、根据下标2.2 删除&#xff1a;del2.3 运算符&#xff1a;、*2.4 计算元组中元素个数&#xff1a;len()2.5 返回元组中元素最大值&#xff1a;max()2.6 返回元组中元素最小值&#xff1a;min()2.7…...

Redis部署-主从模式

目录 单点问题 主从模式 解析主从模式 配置redis主从模式 info replication命令查看复制相关的状态 断开复制关系 安全性 只读 传输延迟 拓扑结构 数据同步psync replicationid offset psync运行流程 全量复制流程 无硬盘模式 部分复制流程 积压缓冲区 实时复…...

全栈冲刺 之 一天速成MySQL

一、为什么使用数据库 数据储存在哪里&#xff1f; 硬盘、网盘、U盘、光盘、内存&#xff08;临时存储&#xff09; 数据持久化 使用文件来进行存储&#xff0c;数据库也是一种文件&#xff0c;像excel &#xff0c;xml 这些都可以进行数据的存储&#xff0c;但大量数据操作…...

服务器运行train.py报错解决

在服务器配置完虚拟环境以及安装完各种所需库后&#xff0c;发现报错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程序时报错&#xff0c;问我怎么解决&#xff0c;程序运行时报如下错误&#xff1a; type ‘Future’ is not a subtype of type ‘int’ in type cast 错误源码 int order Databas…...

Nginx(十二) gzip gzip_static sendfile directio aio 组合使用测试(2)

测试10&#xff1a;开启gzip、sendfile、aio、directio1m&#xff0c;关闭gzip_static&#xff0c;请求/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流程及编译优化模型示例

前言&#xff1a;记录自己安装TVM的流程&#xff0c;以及一个简单的利用TVM编译模型并执行的示例。 1&#xff0c;官网下载TVM源码 git clone --recursive https://github.com/apache/tvmgit submodule init git submodule update顺便完成准备工作&#xff0c;比如升级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&#xff0c;使用try-except可以使程序在发生异常后仍然能够运行。 在try的部分中&#xff0c;当遇到第一个Error&#xff0c;就跳转到except中寻找对应类型的error&#xff0c;后续代码不再执行&#xff0c;如果try中有多个Error&#xff0c;注意顺…...

flutter开发实战-ValueListenableBuilder实现局部刷新功能

flutter开发实战-ValueListenableBuilder实现局部刷新功能 在创建的新工程中&#xff0c;点击按钮更新counter后&#xff0c;通过setState可以出发本类的build方法进行更新。当我们只需要更新一小部分控件的时候&#xff0c;通过setState就不太合适了&#xff0c;这就需要进行…...

通过时间交织技术扩展ADC采样速率的简要原理

前言 数据采集是将自然界中存在的模拟信号通过模数转换器&#xff08;ADC&#xff09;转换成数字信号&#xff0c;再对该数字信号进行相应的接收和处理。数据采集系统作为数据采集的手段&#xff0c;在移动通信、图向采集、无线电等领域有重要作用。随着电子信息技术的飞速发展…...

Prompt Tuning、P-Tuning、Prefix Tuning的区别

一、Prompt Tuning、P-Tuning、Prefix Tuning的区别 1. Prompt Tuning(提示调优) 核心思想:固定预训练模型参数,仅学习额外的连续提示向量(通常是嵌入层的一部分)。实现方式:在输入文本前添加可训练的连续向量(软提示),模型只更新这些提示参数。优势:参数量少(仅提…...

JavaScript 中的 ES|QL:利用 Apache Arrow 工具

作者&#xff1a;来自 Elastic Jeffrey Rengifo 学习如何将 ES|QL 与 JavaScript 的 Apache Arrow 客户端工具一起使用。 想获得 Elastic 认证吗&#xff1f;了解下一期 Elasticsearch Engineer 培训的时间吧&#xff01; Elasticsearch 拥有众多新功能&#xff0c;助你为自己…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

使用van-uploader 的UI组件,结合vue2如何实现图片上传组件的封装

以下是基于 vant-ui&#xff08;适配 Vue2 版本 &#xff09;实现截图中照片上传预览、删除功能&#xff0c;并封装成可复用组件的完整代码&#xff0c;包含样式和逻辑实现&#xff0c;可直接在 Vue2 项目中使用&#xff1a; 1. 封装的图片上传组件 ImageUploader.vue <te…...

ffmpeg(四):滤镜命令

FFmpeg 的滤镜命令是用于音视频处理中的强大工具&#xff0c;可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下&#xff1a; ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜&#xff1a; ffmpeg…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...