( “树” 之 DFS) 687. 最长同值路径 ——【Leetcode每日一题】

news/2024/2/28 4:41:08

687. 最长同值路径

给定一个二叉树的 root ,返回 最长的路径的长度 ,这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。

两个节点之间的路径长度 由它们之间的边数表示。

示例 1:

在这里插入图片描述

输入:root = [5,4,5,1,1,5]
输出:2

示例 2:

在这里插入图片描述

输入:root = [1,4,5,4,4,5]
输出:2

提示:

  • 树的节点数的范围是 [0,104][0, 10^4][0,104]
  • -1000 <= Node.val <= 1000
  • 树的深度将不超过 1000

思路:DFS

分析:

对任意一个节点,有两种可能,最大路径可能经过该节点,或者不经过该节点

  • 最大路径经过该节点时:
    • 若该节点为最大路径的根节点root时, 路径长度左子树的路径长度加上右子树的路径长度
    • 若节点不是最大路径的根节点时,则最大路径的根节点root一定在其父节点上,此时返回其左右子树的路径的最大值
  • 最大路径不经过该节点时,返回0.

设计:(从下往上判断)

根据上述分析,设计递归函数int dfs(TreeNode root)

  • 含义为传入根节点 root, 返回最大路径经过该节点,但是该节点不是最大路径的根节点,即返回其左右子树的路径的最大值
  • 同时设置全局变量path,记录最大路径,在每个节点为根节点时判断更新,即左子树的路径长度加上右子树的路径长度
  • 在递归函数内部,先通过递归 root 的左右子节点,拿到以 root.leftroot.right 为起点的最大路径长度 leftright ,然后以root节点为最大路径的根节点 ,分别判断左右子树的val值是否等于root.val,如果相等则加1,不等则为0
  • 同时更新最大路径path

代码:(Java、C++)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private int path = 0;public int longestUnivaluePath(TreeNode root) {dfs(root);return path;}public int dfs(TreeNode root){if(root == null) return 0;int left = dfs(root.left);int right = dfs(root.right);int leftPath = root.left != null && root.val == root.left.val ? 1 + left : 0;int rightPath = root.right != null && root.val == root.right.val ? 1 + right : 0;path = Math.max(path, leftPath + rightPath); return Math.max(leftPath, rightPath);}
}

C++

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int path = 0;int longestUnivaluePath(TreeNode* root) {dfs(root);return path;}int dfs(TreeNode* root){if(root == NULL) return 0;int left = dfs(root->left);int right = dfs(root->right);int leftPath = root->left != NULL && root->val == root->left->val ? 1 + left : 0;int rightPath = root->right != NULL && root->val == root->right->val ? 1 + right : 0;path = max(path, leftPath + rightPath); return max(leftPath, rightPath);}
};

运行结果:

复杂度分析:

  • 时间复杂度O(n)O(n)O(n),其中 n 为树的结点数目。
  • 空间复杂度O(n)O(n)O(n)。递归栈最坏情况下需要O(n)O(n)O(n)的空间。

题目来源:力扣。

放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!

注: 如有不足,欢迎指正!


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

相关文章

采集工具如何帮助SEO优化关键词

随着互联网的发展&#xff0c;越来越多的企业开始意识到SEO优化对于企业的重要性。SEO优化可以帮助企业提高网站在搜索引擎中的排名&#xff0c;进而吸引更多的潜在客户。而关键词则是SEO优化的核心&#xff0c;如何找到合适的关键词&#xff0c;成为了企业优化的关键。在这里&…

java程序员学前端-Vue3篇

Vue 3 1. TypeScript 1) 动态类型的问题 前面我们讲过 js 属于动态类型语言&#xff0c;例如 function test(obj) { }obj 可能只是个字符串 test(hello, world)obj 也有可能是个函数 test(()>console.log(hello, world))obj 类型不确定&#xff0c;就给后期使用者…

leetcode1427. 字符串的左右移

题目 给定一个包含小写英文字母的字符串 s 以及一个矩阵 shift&#xff0c;其中 shift[i] [direction, amount]&#xff1a; direction 可以为 0 &#xff08;表示左移&#xff09;或 1 &#xff08;表示右移&#xff09;。 amount 表示 s 左右移的位数。 左移 1 位表示移除 s…

Windows应急响应 -Windows日志排查,系统日志,Web应用日志,

「作者简介」&#xff1a;CSDN top100、阿里云博客专家、华为云享专家、网络安全领域优质创作者 「推荐专栏」&#xff1a;对网络安全感兴趣的小伙伴可以关注专栏《网络安全入门到精通》 Windows日志分析一、查看日志二、日志分类三、筛选日志四、事件ID1、安全日志1.1、登录类…

Linux ubuntu更新meson版本

问题描述 在对项目源码用meson进行编译时&#xff0c;可能出现以下错误 meson.build:1:0: ERROR: Meson version is 0.45.1 but project requires > 0.58.0. 或者 meson_options.txt:1:0: ERROR: Unknown type feature. 等等&#xff0c;原因是meson版本跟设置的不适配。 …

【面试】记一次中小公司某一次面试题

文章目录1. MySQL中explain执行计划你比较关注哪些字段&#xff1f;2.char、varchar 和 text的区别&#xff1f;3. int(3)和int(11)查询的区别&#xff1f;4. 字段里NULL和空值的区别&#xff1f;5. spring中怎么解决循环依赖问题&#xff1f;5.1 重新设计5.2 使用注解 Lazy5.3…

WSL下的Kafka开发容器:Docker搭建、API、整合

背景介绍 Kafka是一个分布式流处理平台&#xff0c;可以处理大规模数据流并支持实时数据流的处理。 本文介绍了如何在WSL下使用Docker搭建Kafka容器&#xff0c;并使用Python的kafka-python库和FastAPI框架实现了一个简单的API。同时&#xff0c;还将该服务整合到一个整体的d…

C++之模拟实现map和set

文章目录前言一、迭代器1.begin()和end()2.operator()二、改造红黑树三、map的模拟实现四、set的模拟实现总结前言 基于之前的红黑树和map、set的相关知识&#xff0c;本节我们使用红黑树来模拟实现STL中的map和set。 一、迭代器 使用迭代器可以方便我们对数据结构进行遍历&a…

uni-app:登录与支付-- 三秒后自动跳转

三秒后自动跳转 三秒后自动跳转到登录页面 需求描述&#xff1a;在购物车页面&#xff0c;当用户点击 “结算” 按钮时&#xff0c;如果用户没有登录&#xff0c;则 3 秒后自动跳转到登录页面 在 my-settle 组件的 methods 节点中&#xff0c;声明一个叫做 showTips 的方法&am…

STM-32:I2C外设总线—硬件I2C读写MPU6050

目录一、I2C外设简介二、I2C框图三、I2C基本结构四、主机发送五、主机接收六、I2C的中断请求七、软件/硬件波形对比八、应用实例&#xff1a;硬件I2C读写MPU60508.1接线图8.2程序代码一、I2C外设简介 STM32内部集成了硬件I2C收发电路&#xff0c;可以由硬件自动执行时钟生成、…

智慧停车场解决方案,停车场导航技术怎么实现

停车场导航技术怎么实现&#xff1f;随着城市化的不断发展&#xff0c;停车场建的越来越大&#xff0c;同时也越来越复杂&#xff0c;停车、找车成为很多人感到十分头疼的问题。在这种情况下&#xff0c;一个高效的停车场电子地图应用已经成为城市交通管理中不可缺少的组成部分…

主题切换实现(vue-less)

介绍 本文适合黑白切换或者主题样式偏少的&#xff08;建议&#xff1a;2-10种&#xff09;&#xff1b;主题越多&#xff0c;样式会越多。理论上无限套。本文适合已经写好了一套主题&#xff0c;然后需求增加第二套或者多套主题&#xff08;最好小于10套&#xff0c;当然也可…

leetcode455. 分发饼干

题目描述解题思路执行结果leetcode455. 分发饼干 .题目描述 假设你是一位很棒的家长&#xff0c;想要给你的孩子们一些小饼干。但是&#xff0c;每个孩子最多只能给一块饼干。 对每个孩子 i&#xff0c;都有一个胃口值 g[i]&#xff0c;这是能让孩子们满足胃口的饼干的最小尺寸…

4.6--计算机网络之TCP篇之TCP的基本认识--(复习+深入)---好好沉淀,加油呀

1.TCP 头格式有哪些&#xff1f; 序列号&#xff1a; 在建立连接时由计算机生成的随机数作为其初始值&#xff0c;通过 SYN 包传给接收端主机&#xff0c;每发送一次数据&#xff0c;就「累加」一次该「数据字节数」的大小。 用来解决网络包乱序问题。 确认应答号&#xff1a; …

winform从入门到精通

环境 开发工具 visual studio 2019 16.11 community 基础框架 framework4.8 .net5需要开发工具小版本16.8以上 winform开发入门 windows桌面端应用开发框架 https://github.com/dotnet/winforms c#基础 partial class 创建项目 项目结构 引用&#xff1a;所依赖的系统库 …

关于 CSDN-AI 机器人 programmer_ada —— 阿达·洛夫莱斯(Ada Lovelace)

收到早期文章的一条新评论&#xff1a; 文笔和内容稍稍透漏着机器人的风格&#xff0c;打开主页果不其然 看到个人介绍中的巴贝奇的分析机&#xff0c;突然觉得头像很是眼熟。 最近刚读了《人工智能简史》&#xff0c;第4章——从汇编语言到TensorFlow&#xff0c;人工智能的…

LightGBM论文翻译

0.摘要 Gradient Boosting Decision Tree (GBDT)是一个非常流行的机器学习算法&#xff0c;却只有像XGBoost和pGBRT的一些实现。尽管许多工程上的优化方案已经在这些实现中应用了&#xff0c;但是当特征维度较高和数据量巨大的时候&#xff0c;仍然存在效率和可扩展性的问题。…

今年又是一年自媒体高峰期你是否抓住了

影视剪辑容易遇到哪些问题&#xff1a; 1、视频格式格式不对&#xff0c;剪辑软件不支持&#xff1b; 2、视频封面不会做&#xff1b; 3、PR导出视频时&#xff0c;没办法做其他事&#xff0c;效率不高&#xff1b; 4、自己配音不好听&#xff0c;配音软件又不好找&#xf…

uni-app:登录与支付--用户信息

用户信息 实现用户头像昵称区域的基本布局 在 my-userinfo 组件中&#xff0c;定义如下的 UI 结构&#xff1a; <template><view class"my-userinfo-container"><!-- 头像昵称区域 --><view class"top-box"><image src"…

Vulnhub靶场DC1-2练习

目录0x00 准备0x01 信息收集0x02 漏洞利用与攻击0x03 思路总结0x00 准备 下载连接&#xff1a;https://download.vulnhub.com/dc/DC-2.zip 介绍&#xff1a;Just like with DC-1, there are five flags including the final flag.Please note that you will need to set the …
最新文章