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

树形 DP:树的直径

leetCode 104.二叉树的最大深度104. 二叉树的最大深度 - 力扣(LeetCode)

class Solution {
public:int maxDepth(TreeNode* root) {if(root == nullptr) return 0;int lDepth = maxDepth(root->left);int rDepth = maxDepth(root->right);return max(lDepth,rDepth)+1;}
};

leetCode 543.二叉树的直径 543. 二叉树的直径 - 力扣(LeetCode)

换个角度看直径:从一个叶子出发向上,在某个节点“拐弯”,向下到达另一个叶子,得到了由两条链拼起来的路径。(也可能只有一条链)

算法:遍历二叉树,在计算最长链的同时,顺带把直径算出来

  • 在当前节点“拐弯”的直径长度 = 左子树的最长链 + 右子树的最长链 + 2
  • 返回给父节点的是以当前节点为根的子树的最长链 = max(左子树的最长链,右子树的最长链)+1
class Solution {
public:int diameterOfBinaryTree(TreeNode* root) {int ans=0;function<int(TreeNode*)>dfs =[&](TreeNode* node) -> int {if(node == nullptr) return -1;// 下面+1后,对于叶子节点就刚好是 0int left = dfs(node->left);int right = dfs(node->right);ans = max(ans,left+right+2);return max(left,right)+1; //当前子树最大链长};dfs(root);return ans;}
};

leetCode 124.二叉树中的最大路径和 124. 二叉树中的最大路径和 - 力扣(LeetCode)

算法:遍历二叉树,在计算最大链和的同时,顺带更新答案的最大值

  • 在当前节点 "拐弯"最大路径和 = 左子树最大链和 + 右子树最大链和 + 当前节点值
  • 返回给父节点的是max(左子树最大链和,右子树最大链和)+当前节点值。如果这个值是负数,则返回 0 
class Solution:def maxPathSum(self, root: Optional[TreeNode]) -> int:ans = -infdef dfs(node):if node is None:return 0l_val = dfs(node.left)r_val = dfs(node.right)nonlocal ansans = max(ans,l_val+r_val+node.val)return max(max(l_val,r_val) + node.val,0)dfs(root)return ans

2246.相邻字符不同的最长路径(1245.树的直径)2246. 相邻字符不同的最长路径 - 力扣(LeetCode)

class Solution {
public:int longestPath(vector<int>& parent, string s) {int n = parent.size();vector<vector<int>> g(n);for(int i=1;i<n;i++) {g[parent[i]].push_back(i);}int ans = 0;function<int(int)> dfs = [&](int x) -> int {int maxLen = 0;for (int y : g[x]) {int len = dfs(y) + 1;if (s[y] != s[x]) {ans = max(ans, maxLen + len);maxLen = max(maxLen, len);}}return maxLen;};dfs(0);return ans+1;}
};// -1 0 0 1 1 2
//  0 1 2 3 4 5//   0:[1,2]
//   1:[3,4]
//   2:[5]

推荐文章和参考视频:

树形 DP:树的直径【基础算法精讲 23】_哔哩哔哩_bilibili

543. 二叉树的直径 https://leetcode.cn/problems/diameter-of-binary-tree/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-taqma/
124. 二叉树中的最大路径和 https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/shi-pin-che-di-zhang-wo-zhi-jing-dpcong-n9s91/
2246. 相邻字符不同的最长路径 https://leetcode.cn/problems/longest-path-with-different-adjacent-characters/solution/by-endlesscheng-92fw/ 

相关文章:

树形 DP:树的直径

leetCode 104.二叉树的最大深度104. 二叉树的最大深度 - 力扣&#xff08;LeetCode&#xff09; class Solution { public:int maxDepth(TreeNode* root) {if(root nullptr) return 0;int lDepth maxDepth(root->left);int rDepth maxDepth(root->right);return max(l…...

【Python百宝箱】第三维度的魔法:探索Python游戏世界

Python在游戏开发中的魔力 前言 游戏开发一直是计算机科学中最引人入胜和具有挑战性的领域之一。随着技术的不断进步&#xff0c;开发者们寻找着更快、更灵活的工具来实现他们的创意。在这个探索的过程中&#xff0c;Python以其简洁、易学和强大的特性成为了游戏开发的热门选…...

3ds Max 电脑配置建议 | 建模+渲染选专业显卡or游戏显卡?

&#xfeff;使用3ds Max进行建模和渲染时&#xff0c;选择合适的电脑配置非常重要。比如在硬件选择上&#xff0c;究竟选购游戏显卡还是专业显卡呢&#xff1f;本文将为你详细介绍游戏显卡和专业显卡的区别&#xff0c;并提供配置建议&#xff0c;助你作出明智的决策。 &#…...

水淹七军(递归,又是递归)

北大2023级最强新生问我的&#xff0c;最后他的问题说是重写了一遍就解决了 乐死了&#xff0c;有的时候根本看不出源代码漏了哪里 我的思路是&#xff1a; 一个数组记录本次放水所经过的格子&#xff0c;经过的不再递归 一个数组记录地图上各地点的高度 一个数组记录地图…...

Stable Video Diffusion重磅发布,快来看看哪些功能

本周&#xff0c;有关 OpenAI 宫斗的报道占据了Ai圈版面的主导地位&#xff0c;吃够了奥特曼的大瓜。我们来看看Stability AI刚发布的Stable Video Diffusion&#xff0c;这是一种通过对现有图像进行动画处理来生成视频的 AI 模型。基于 Stability 现有的Stable Diffusion文本到…...

城市NOA到来时刻,车企密集上车NVIDIA

作者 |张祥威 编辑 |德新 基于双NVIDIA DRIVE Orin实现城市NOA&#xff0c;已是今天国内汽车行业的主流做法。 这款芯片获得广泛的市场认同&#xff0c;用时仅一年多。去年3月&#xff0c; NVIDIA DRIVE Orin正式投产&#xff0c;此后从造车新势力一路来到更多自主品牌的车内&…...

Linux后台运行Python的py文件,如何使ssh工具退出后仍能运行

常规运行 python3 mysqlbak.py ssh工具退出后&#xff0c;或ctrlc中断后&#xff0c;程序将不在运行 后台运行 nohup python3 mysqlbak.py > mysqlbak.log & > mysqlbak.log为可选项&#xff0c;输出日志到指定文件&#xff0c;如果不写&#xff0c;输出日志到nohup…...

Excel中出现“#NAME?”怎么办?(文本原因)

excel 单元格出现 #NAME? 错误的原因有二&#xff1a; 函数公式输入不对导致 #NAME? 错误。 在单元格中字符串的前面加了号&#xff0c;如下图中的--GoJG7sEe6RqgTnlUcitA&#xff0c;本身我们想要的是--GoJG7sEe6RqgTnlUcitA&#xff0c;但因为某些不当的操作在前面加了号&…...

superset 后端增加注册接口

好烦啊-- &#xff1a;< 1.先定义modes: superset\superset\models\user.py # Licensed to the Apache Software Foundation (ASF) under one # or more contributor license agreements. See the NOTICE file # distributed with this work for additional information…...

利用 React 和 Bootstrap 进行强大的前端开发

文章目录 介绍React 和 Bootstrap设置环境使用 Bootstrap 创建 React 组件React-Bootstrap 组件结论 介绍 创建响应式、交互式和外观引人入胜的 Web 界面是现代前端开发人员的基本技能。幸运的是&#xff0c;借助 React 和 Bootstrap 等工具的出现&#xff0c;制作这些 UI 变得…...

深度学习之基于Pytorch照片图像转漫画风格网络系统

欢迎大家点赞、收藏、关注、评论啦 &#xff0c;由于篇幅有限&#xff0c;只展示了部分核心代码。 文章目录 一项目简介 二、功能三、系统四. 总结 一项目简介 以下是一个基本的设计介绍&#xff1a; 数据准备&#xff1a;收集足够的真实照片和漫画图像&#xff0c;用于训练模…...

解决No Feign Client for loadBalancing defined,修改Maven依赖

Spring微服务报错&#xff1a; java.lang.IllegalStateException:FactoryBean threw exception on object creation; nested exception is java.lang.IllegalStateException: No Feign Client for loadBalancing defined. Did you forget to include spring-cloud-starter-netf…...

友思特分享 | Neuro-T:零代码自动深度学习训练平台

来源&#xff1a;友思特 智能感知 友思特分享 | Neuro-T&#xff1a;零代码自动深度学习训练平台 欢迎关注虹科&#xff0c;为您提供最新资讯&#xff01; 工业自动化、智能化浪潮涌进&#xff0c;视觉技术在其中扮演了至关重要的角色。在汽车、制造业、医药、芯片、食品等行业…...

基于动量的梯度下降

丹尼尔林肯 (Daniel Lincoln)在Unsplash上拍摄的照片 一、说明 基于动量的梯度下降是一种梯度下降优化算法变体&#xff0c;它在更新规则中添加了动量项。动量项计算为过去梯度的移动平均值&#xff0c;过去梯度的权重由称为 Beta 的超参数控制。 这有助于解决与普通梯度下降相…...

ELK+kafka+filebeat企业内部日志分析系统

1、组件介绍 1、Elasticsearch&#xff1a; 是一个基于Lucene的搜索服务器。提供搜集、分析、存储数据三大功能。它提供了一个分布式多用户能力的全文搜索引擎&#xff0c;基于RESTful web接口。Elasticsearch是用Java开发的&#xff0c;并作为Apache许可条款下的开放源码发布…...

MyBatis-Plus: 简化你的MyBatis应用

MyBatis-Plus: 简化你的MyBatis应用 在Java开发中&#xff0c;MyBatis一直是一个受欢迎的持久层框架&#xff0c;提供了灵活的数据访问方式。然而&#xff0c;MyBatis的使用往往涉及许多样板代码&#xff0c;这在一定程度上增加了开发的复杂性。这里&#xff0c;MyBatis-Plus&…...

在 go 的项目中使用验证器

1&#xff1a;使用validate 包验证&#xff1a; 安装包&#xff1a; go get github.com/go-playground/validator/v10 package controllerimport ("fmt""github.com/gin-gonic/gin""github.com/go-playground/validator/v10""net/http&quo…...

Handler系列-sendMessage和post的区别

sendMessage和post基本一样&#xff0c;区别在于post的Runnable会被赋值给Message的callback&#xff0c;在最后调用dispatchMessage的时候&#xff0c;callback会被触发执行。 1.sendMessage 调用sendMessageDelayed发送消息 public class Handler {public final boolean s…...

java中 自动装箱与拆箱,基本数据类型,java堆与栈,面向对象与面向过程

文章目录 自动装箱与拆箱基本数据类型与包装类的区别&#xff08;int 和 Integer 有什么区别&#xff09;应用场景的区别&#xff1a; 堆和栈的区别重点来说一下堆和栈&#xff1a;那么堆和栈是怎么联系起来的呢? 堆与栈的区别 很明显&#xff1a;延伸&#xff1a;关于Integer…...

C语言第二十八弹--输入一个非负整数,返回组成它的数字之和

C语言求输入一个非负整数&#xff0c;返回组成它的数字之和 方法一、递归法 思路&#xff1a;设计一个初始条件&#xff0c;通过递归获取非负整数的个位&#xff0c;不断接近递归条件即可。 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h>int DigitSum(int n) {…...

Linux应用开发之网络套接字编程(实例篇)

服务端与客户端单连接 服务端代码 #include <sys/socket.h> #include <sys/types.h> #include <netinet/in.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <arpa/inet.h> #include <pthread.h> …...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

深入理解JavaScript设计模式之单例模式

目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式&#xff08;Singleton Pattern&#…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

MFC 抛体运动模拟:常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...