​LeetCode解法汇总​979. 在二叉树中分配硬币

news/2024/2/28 12:33:37

目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给定一个有 N 个结点的二叉树的根结点 root,树中的每个结点上都对应有 node.val 枚硬币,并且总共有 N 枚硬币。

在一次移动中,我们可以选择两个相邻的结点,然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点,或者从子结点移动到父结点。)。

返回使每个结点上只有一枚硬币所需的移动次数。

示例 1:

输入:[3,0,0]
输出:2
解释:从树的根结点开始,我们将一枚硬币移到它的左子结点上,一枚硬币移到它的右子结点上。

示例 2:

输入:[0,3,0]
输出:3
解释:从根结点的左子结点开始,我们将两枚硬币移到根结点上 [移动两次]。然后,我们把一枚硬币从根结点移到右子结点上。

示例 3:

输入:[1,0,2]
输出:2

示例 4:

输入:[1,0,0,null,3]
输出:4

提示:

  1. 1<= N <= 100
  2. 0 <= node.val <= N

解题思路:

* 解题思路:

* 其实这道题和平衡二叉树很像。

* 我们构建两颗树,

* 第一颗树numMap,记录每个节点及其子节点应该有多少个硬币。

* 第二颗树sumMap,记录每个节点及其子节点当前有多少个硬币。

* 每个节点当前具有的,减去应该具有的硬币数量,其差值的绝对值就是每个节点应该送出或者接受的数量。

* 求这个差值的和就是我们想要的结果。

代码:

class Solution979
{
public:int getTreeNodeNum(TreeNode *node, std::map<TreeNode *, int> &numMap){if (node == nullptr){return 0;}int num = 1;num += getTreeNodeNum(node->left, numMap);num += getTreeNodeNum(node->right, numMap);numMap[node] = num;return num;}int getTreeNodeSum(TreeNode *node, std::map<TreeNode *, int> &sumMap){if (node == nullptr){return 0;}int sum = node->val;sum += getTreeNodeSum(node->left, sumMap);sum += getTreeNodeSum(node->right, sumMap);sumMap[node] = sum;return sum;}int distributeCoins(TreeNode *root){int sum = 0;std::map<TreeNode *, int> numMap;std::map<TreeNode *, int> sumMap;getTreeNodeNum(root, numMap);getTreeNodeSum(root, sumMap);// std::cout << "Value: " << sumMap.size() << std::endl;int result = 0;for (auto it = numMap.begin(); it != numMap.end(); ++it){int sum = sumMap[it->first];int num = it->second;result += abs(sum - num);}return result;}
};


http://www.ppmy.cn/news/879793.html

相关文章

2023年7月14日,ArrayList底层

集合框架图&#xff1a; 集合和数组的区别 AarrayList ArrayList底层实现原理 ArrayList的底层实现是基于数组的动态扩容。 初始容量&#xff1a;当创建一个新的ArrayList对象时&#xff0c;它会分配一个初始容量为10的数组。这个初始容量可以根据需求进行调整。 //表示默认的…

【QT】——Base64加解密

介绍 用 记事本 打开 exe、jpg、pdf 这些文件时&#xff0c;我们都会看到一大堆乱码&#xff0c;因为二进制文件包含很多无法显示和打印的字符。如果要让记事本这样的文本处理软件 能 处理二进制数据&#xff0c;如使用 json 保存二进制信息&#xff0c;需要先把数据先做一个 …

python数据挖掘基础环境安装和使用

文章目录 一&#xff0e;安装python环境二、库的安装2.1 使用pip命令安装virtualenvv扩展&#xff1a;cmd无法使用pip&#xff0c;报错&#xff1a;Fatal error in launcher: Unable to create process using ... 2.2 安装virtualenvwrapper-win2.3 新建一个用于人工智能环境的…

周鸿祎谈产品(演讲全文)

《张小龙通过微信谈产品完整版&#xff1a;如何把产品做简单》技惊四座&#xff0c;如今周鸿祎这个360“首席产品体验师”在近期一次会议上畅谈了他的产品观。 360周鸿祎 以下为周鸿祎演讲全文&#xff0c;略有删节&#xff1a; 我刚才来的时候&#xff0c;会议主办方跟我讲&am…

周鸿祎:像怀胎一样怀产品

周鸿祎谈产品&#xff1a;像怀胎一样怀产品&#xff0c;要厚着脸皮听批评&#xff08;转&#xff09; 我刚才来的时候&#xff0c;会议主办方跟我讲&#xff0c;今天来交流的很多人是设计师、产品经理&#xff0c;据说还有50位公司的高管&#xff0c;我今天希望跟大家有一个交流…

周鸿祎:如何做好产品经理

我刚才来的时候&#xff0c;会议主办方跟我讲&#xff0c;今天来交流的很多人是设计师、产品经理&#xff0c;据说还有 50 位公司的高管&#xff0c;我今天希望跟大家有一个交流&#xff0c;对很多公司高管来讲&#xff0c;我其实有一个建议&#xff0c;过去这种公司分工特别明…

宋浩高等数学笔记(一)函数与极限

b站宋浩老师的高等数学网课&#xff0c;全套笔记已记完&#xff0c;不定期复习并发布更新。 章节顺序与同济大学第七版教材所一致。

吴恩达机器学习2022-Jupyter-用scikitlearn实现线性回归

1可选实验:使用Scikit-Learn进行线性回归 有一个开源的、商业上可用的机器学习工具包&#xff0c;叫做 scikit-learn。本工具包包含您将在本课程中使用的许多算法的实现。 1.1工具 您将利用 scikit-learn 以及 matplotlib 和 NumPy 中的函数。 2线性回归封闭式解决方案 Sc…

电容0.1uF和104有什么区别?

1040.1uF &#xff0c;容量都是一样的&#xff01; 在电路图中经常看到的是0.1UF&#xff0c;有时候也看到104&#xff0c;没有什么区别&#xff0c;标法不一罢了&#xff01; 0.1uF是直标法&#xff0c;而104是数码法。 直标法&#xff1a; 直接标出电容的大小&#xff0c;单…

电气器件系列十五:CBB电容

CBB61是一种CBB电容&#xff0c;CBB是聚丙烯电容的意思&#xff0c;61是它的型号&#xff0c;它是一种普遍用于交流市电电源供电的单相电动机的起动和运转电容&#xff0c;我们称之为启动电容&#xff08;有时候也称为电容&#xff09;。在电动水泵&#xff0c;各种交流风扇、交…

迷你折叠洗衣机UL测试项目

迷你折叠洗衣机外贸出口上架亚马逊美国站需要提交UL1776测试报告&#xff0c;必须是有ISO 17025资质的实验室出具的测试报告才能正常销售和恢复链接。 所谓折叠洗衣机&#xff0c;显而易见是可折叠的&#xff0c;听起来就像属于随用随放、日常不占用空间的产品&#xff0c;感觉…

单相电机正反转接线图_单相电机电容接线图

220V交流单相电机起动方式大概分一下几种&#xff1a;第一种&#xff0c;分相起动式&#xff0c;如图1所示&#xff0c;系由辅助起动绕组来辅助启动&#xff0c;其起动转矩不大。运转速率大致保持定值。主要应用于电风扇,空调风扇电动机&#xff0c;洗衣机等电机。接线图 第二种…

电容式触摸感应按键解决方案AD

前一段时间,做了一个使用 HT45R35 芯片的触摸按键项目,属于是芯片自带专门应用于触摸键功能的"专用芯片".近日,再次对触摸按键进行实践----使用 AD 转换方式.这样,就不要专门功能的芯片了.同时,调试更加简单方便,也没有了许多限制. 下图是一个该实践的原理图,每一个…

220V电容启动交流电机

这种电机一般用在对转速稳定性要求不大&#xff0c;扭矩较大的场合。如&#xff1a;点钞机、洗衣机里的电机。 一般长这样&#xff1a; 然后它的旁边一般还能找到一个长这样的黑色大电容&#xff1a; CBB61电容上面的数字含义为&#xff1a;CBB代表聚苯乙烯电容器。61表示型号…

5.3 常见的电感式和电容式感测原理及应用

常见的电感式和电容式感测应用 1、电感式和电容式工作原理1.1 电感式感测工作原理1.2 电容式感测工作原理 2 FDC&#xff1a;电容式液位感测2.1 电容技术在液位感测中的优势2.2 电容式液位感测入门 3 LDC&#xff1a;电感式触控按钮4 LDC&#xff1a;增量编码器和事件计数5 LDC…

【利用电容-数字转换器检测液位】

利用电容-数字转换器检测液位 输液和输血等程序要求监控液体的确切数量&#xff0c;因此这些应用需要采用精确、易于实施的方法来实现液位的检测。本文描述24位电容-数字转换器和液位检测技术&#xff0c;可通过测量电容对液位进行高性能检测。 常见得电容数字转换芯片有PCAP0…

计算机控制电机启动接线图,详解单相电机电容接线图

220V交流单相电机起动方式大概分一下几种&#xff1a;第一种&#xff0c;分相起动式&#xff0c;如图1所示&#xff0c;系由辅助起动绕组来辅助启动&#xff0c;其起动转矩不大。运转速率大致保持定值。主要应用于电风扇&#xff0c;空调风扇电动机&#xff0c;洗衣机等电机。接…

应用在洗衣机触摸屏中的触摸芯片

由于洗衣机通常放置在污渍、灰尘、水污集中的位置&#xff0c;用户需要经常清洗洗衣机的表面&#xff0c;在清洗过程中发现&#xff0c;触摸按键容易损坏或进水&#xff0c;致使触摸按键失灵。触摸屏感应到手指的触摸是因为当手指触摸屏幕上的一个具体位置时&#xff0c;相当于…

秒懂电容自举电路

自举电容的核心原理是&#xff1a;电容两端电压不能突变。 从这句话中&#xff0c;我们可以获取到两个关键字&#xff1a;两端电压、不能突变。 两端电压指的是电容一边相对另一边的电压&#xff0c;我们知道电压本身就是个参考值&#xff08;一般认定参考GND&#xff0c;认定…

单片机课程设计洗衣机c语言,基于51单片机洗衣机控制器的设计(附程序)☆

基于51单片机洗衣机控制器的设计(附程序)☆(任务书,开题报告,中期检查表,毕业论文21000字,程序) 摘 要 洗衣机是人们日常生活中常见的一种家电,已经成为人们生活中不可缺少的家用电器。在工业生产中应用也十分广泛。但是传统的基于继电器的控制,已经不能满足人们对洗衣机的自…
最新文章