深度优先搜索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;
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/221191.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

15.(vue3.x+vite)组件间通信方式之默认插槽(匿名插槽)

前端技术社区总目录(订阅之前请先查看该博客) 示例效果 默认插槽(匿名插槽) 插槽 slot 通常用于两个父子组件之间,最常见的应用就是我们使用一些 UI 组件库中的弹窗组件时,弹窗组件的内容是可以让我们自定义的,这就是使用了插槽的原理。 (1)slot 是 Vue中的内置标签…

使用 PyTorch 进行 K 折交叉验证

一、说明 中号机器学习模型在训练后必须使用测试集进行评估。我们这样做是为了确保模型不会过度拟合&#xff0c;并确保它们适用于现实生活中的数据集&#xff0c;与训练集相比&#xff0c;现实数据集的分布可能略有偏差。 但为了使您的模型真正稳健&#xff0c;仅仅通过训练/测…

在AWS Lambda上部署标准FFmpeg工具——自定义层的方案

大纲 1 确定Lambda运行时环境1.1 Lambda系统、镜像、内核版本1.2 运行时1.2.1 Python1.2.2 Java 2 打包FFmpeg3 创建Lambda的Layer4 测试4.1 创建Lambda函数4.2 附加FFmpeg层4.3 添加测试代码4.4 运行测试 参考文献 FFmpeg被广泛应用于音/视频流处理领域。对于简单的需求&#…

Databend 开源周报第 122 期

Databend 是一款现代云数仓。专为弹性和高效设计&#xff0c;为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务&#xff1a;https://app.databend.cn 。 Whats On In Databend 探索 Databend 本周新进展&#xff0c;遇到更贴近你心意的 Databend 。 支持链式函数调…

Gee教程6.模板(HTML Template)

这一章节的内容是介绍 Web 框架如何支持服务端渲染的场景 实现静态资源服务(Static Resource)。支持HTML模板渲染。 这一章节很多内容是基于net/http库的&#xff0c;该库已经实现了很多静态文件和HMML模板的相关功能的了。 静态文件 网页的三剑客&#xff0c;JavaScript、C…

28、pytest实战:获取多用户鉴权

前提 测试过程中有用户体系&#xff0c;例如包括管理员、商家、用户角色&#xff0c;不同测试用例需要使用不同角色来操作&#xff0c;操作权限根据用户的鉴权来判断实现。 技能点 建立全局变量文件&#xff0c;保存账号相关信息获取鉴权信息变为module级别fixture&#xff…

mac批量修改图片格式

1. 当前窗口在word文档&#xff0c;选择工具-》宏-》点击宏 2. 弹出弹框&#xff0c;起个宏名1&#xff0c;点击2添加一个宏。 输入以下代码&#xff1a; Sub 图片格式统一()图片格式统一 宏Dim iDim Height, WeightHeight 200 改成自己的高度Weight 350 改成自己的宽度On E…

基于Java swing 学生选课成绩管理系统

Java swing 学生选课成绩管理系统 在SQL Server下建库、建表、建约束、建视图、建触发器、建角色、建用户等&#xff0c;并录入必要的数据。 编程实现至少3个模块 登录模块&#xff1a;输入用户名、密码&#xff0c;选择身份&#xff08;通过检索出数据库里现有的用户身份&…

分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测

分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测 目录 分类预测 | Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测分类效果基本描述程序设计参考资料 分类效果 基本描述 1.Matlab实现OOA-CNN-SVM鱼鹰算法优化卷积支持向量机分类预测&#xff0…

智能优化算法应用:基于闪电连接过程算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于闪电连接过程算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于闪电连接过程算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.闪电连接过程算法4.实验参数设定5.算…

开始使用高性能、低延迟的对象存储服务 Amazon S3 Express One Zone

全新的对象存储服务 Amazon S3 Express One Zone 旨在提供比 Amazon S3 Standard 高出10倍的性能&#xff0c;同时每秒可处理数十万个请求&#xff0c;并且延迟始终保持在个位数毫秒级&#xff0c;因此非常适合存储最常访问的数据和要求最苛刻的应用程序。将对象存储和复制到单…

【链表Linked List】力扣-24 两两交换链表中的节点

目录 题目描述 解题过程 题目描述 给你一个链表&#xff0c;两两交换其中相邻的节点&#xff0c;并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题&#xff08;即&#xff0c;只能进行节点交换&#xff09;。 示例 1&#xff1a; 输入&#xff1a;he…

⭐ Unity里 用OpenCv 插件 将图片生成Gcode

现在遇到一个需求&#xff0c;用Unity里用图片生成Gcode 告知硬件让它去画出来 翻阅了一些资料&#xff0c;最后决定用OpenCV去做 下图左侧是生成的Gcode文件 右侧是要画的图片 话不多说直接上代码 using System.IO; using UnityEngine; using OpenCVForUnity.CoreModule; …

第十五届蓝桥杯模拟赛B组(第二期)C++

前言&#xff1a; 第一次做蓝桥模拟赛的博客记录&#xff0c;可能有很多不足的地方&#xff0c;现在将第十五届蓝桥杯模拟赛B组&#xff08;第二期&#xff09;的题目与代码与大家进行分享&#xff0c;我是用C做的&#xff0c;有好几道算法题当时自己做的也是一脸懵&#xff0c…

财报解读:立足海外音视频直播战场,欢聚的BIGO盾牌还需加强?

如今&#xff0c;音视频社交平台出海早已不是新鲜事&#xff0c;随着时间推移&#xff0c;一批“坚定全球化不动摇”的企业也实现突围&#xff0c;站在出海舞台中心。 若提到中国企业出海范本&#xff0c;欢聚集团定是绕不开的存在。作为最早一批出海的中国互联网企业&#xf…

CS144(2023 Spring)Lab 0:networking warmup(环境搭建 webget bytestream)

文章目录 前言其他笔记相关链接 1. Set up GNU/Linux on your computer2. Networking by hand3. Writing a network program using an OS stream socket3.1 Linux配置3.2 C规范3.3 Writing webget3.3.1 实现3.3.2 测试 4. An in-memory reliable byte stream4.1 思路分析4.2 代…

记录 | vscode设置自动换行

右上菜单栏 -> 查看 -> 打开自动换行 或者还有种方式&#xff0c;如下&#xff0c; 左下角小齿轮&#xff0c;点击设置 然后输入 Editor: Word Wrap &#xff0c;把开关打开为 on

扩散模型实战(十四):扩散模型生成音频

推荐阅读列表&#xff1a; 扩散模型实战&#xff08;一&#xff09;&#xff1a;基本原理介绍 扩散模型实战&#xff08;二&#xff09;&#xff1a;扩散模型的发展 扩散模型实战&#xff08;三&#xff09;&#xff1a;扩散模型的应用 扩散模型实战&#xff08;四&#xff…

使用 Go Modules 管理依赖:简明教程

一、GoLang 中包的介绍和定义 包&#xff08;package&#xff09;是多个 Go 源码的集合&#xff0c;是一种高级的代码复用方案Go 语言为我们提供了很多内置包&#xff0c;如 fmt、strconv、strings、sort、errors、times、encoding/json、os、io 等Golang 中的包可以分为三种&…

C# WPF上位机开发(图形显示软件)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 在实际应用中&#xff0c;有一种情况就是&#xff0c;我们需要经常对数据进行图形化显示&#xff0c;这样会比较直观一点。比如经济统计里面的同比…