LeetCode-543. 二叉树的直径【树 深度优先搜索 二叉树】

LeetCode-543. 二叉树的直径【树 深度优先搜索 二叉树】

  • 题目描述:
  • 解题思路一:DFS
  • 解题思路二:另一种写法DFS
  • 解题思路三:0

题目描述:

给你一棵二叉树的根节点,返回该树的 直径 。

二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。

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

示例 1:
在这里插入图片描述
输入:root = [1,2,3,4,5]
输出:3
解释:3 ,取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。

示例 2:

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

提示:

树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100

解题思路一:DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node):
            if not node:
                return -1 # 下面 +1 后,对于叶子节点就刚好是 0
            l_ren = dfs(node.left) + 1 # 左子树最大链长+1
            r_ren = dfs(node.right) + 1 # 右子树最大链长+1
            nonlocal ans
            ans = max(l_ren + r_ren, ans) # 两条链拼成路径
            return max(l_ren, r_ren)  # 当前子树最大链长
        dfs(root)
        return ans

时间复杂度:O(n)
空间复杂度:O(n)

解题思路二:另一种写法DFS

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    
    def __init__(self):
        self.max = 0
    
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.depth(root)
        
        return self.max
        
    def depth(self, root):
        if not root:
            return 0
        l = self.depth(root.left)
        r = self.depth(root.right)
        '''每个结点都要去判断左子树+右子树的高度是否大于self.max,更新最大值'''
        self.max = max(self.max, l+r)
        
        # 返回的是高度
        return max(l, r) + 1

时间复杂度:O(n)
空间复杂度:O(n)

解题思路三:0


时间复杂度:O(n)
空间复杂度:O(n)

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

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

相关文章

不能在主机和虚拟机之间拷贝文本(虚拟机ubuntu16.04)

问题 ubuntu16.04不能在主机和虚拟机之间拷贝文本。 原因 vmware tools没安装好。 解决办法 重新安装vmware tools&#xff0c;步骤入下&#xff1a; 让虚拟机加载C:\Program Files (x86)\VMware\VMware Workstation\linux.iso光盘文件&#xff0c;设置如下&#xff1a; …

C++的并发世界(四)——线程传参

1.全局函数作为传参入口 #include <iostream> #include <thread> #include <string>void ThreadMain(int p1,float p2,std::string str) {std::cout << "p1:" << p1 << std::endl;std::cout << "p2:" <<…

Linux安装conda

目录 conda是什么简介conda与miniconda、anaconda的关系 安装下载文件bash安装激活软件检查安装是否成功配置镜像源 创建环境 conda是什么 简介 conda是一个开源的包管理器和环境管理器&#xff0c;用于安装、运行和更新包和它们的依赖项。它可以轻松地在计算机上创建隔离的环…

刷题DAY44 | 完全背包问题 LeetCode 518-零钱兑换 II 377-组合总和 Ⅳ

完全背包问题模版 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]&#xff0c;得到的价值是value[i] 。每件物品都有无限个&#xff08;也就是可以放入背包多次&#xff09;&#xff0c;求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题…

《UE5_C++多人TPS完整教程》学习笔记29 ——《P30 Blaster 角色(Blaster Character)》

本文为B站系列教学视频 《UE5_C多人TPS完整教程》 —— 《P30 Blaster 角色&#xff08;Blaster Character&#xff09;》 的学习笔记&#xff0c;该系列教学视频为 Udemy 课程 《Unreal Engine 5 C Multiplayer Shooter》 的中文字幕翻译版&#xff0c;UP主&#xff08;也是译…

网络原理 - HTTP / HTTPS(3)——http响应

目录 一、认识 “状态码”&#xff08;status code&#xff09; 常见的状态码 &#xff08;1&#xff09;200 OK &#xff08;2&#xff09;404 Not Found &#xff08;3&#xff09;403 ForBidden &#xff08;4&#xff09;405 Method Not Allowed &#xff08;5&…

从零到一:基于 K3s 快速搭建本地化 kubeflow AI 机器学习平台

背景 Kubeflow 是一种开源的 Kubernetes 原生框架&#xff0c;可用于开发、管理和运行机器学习工作负载&#xff0c;支持诸如 PyTorch、TensorFlow 等众多优秀的机器学习框架&#xff0c;本文介绍如何在 Mac 上搭建本地化的 kubeflow 机器学习平台。 注意&#xff1a;本文以 …

从头开发一个RISC-V的操作系统(二)RISC-V 指令集架构介绍

文章目录 前提ISA的基本介绍ISA是什么CISC vs RISCISA的宽度 RISC-V指令集RISC-V ISA的命名规范模块化的ISA通用寄存器Hart特权级别内存管理与保护异常和中断 目标&#xff1a;通过这一个系列课程的学习&#xff0c;开发出一个简易的在RISC-V指令集架构上运行的操作系统。 前提…

JavaSE-11笔记【多线程2(+2024新)】

文章目录 6.线程安全6.1 线程安全问题6.2 线程同步机制6.3 关于线程同步的面试题6.3.1 版本16.3.2 版本26.3.3 版本36.3.4 版本4 7.死锁7.1 多线程卖票问题 8.线程通信8.1 wait()和sleep的区别&#xff1f;8.2 两个线程交替输出8.3 三个线程交替输出8.4 线程通信-生产者和消费者…

硬件了解 笔记 2

CPU 内存控制器&#xff1a;负责读写数据 代理系统和平台IO&#xff1a;与主板上的芯片组通信&#xff0c;并管理PC中其他组件之间的数据流 主板&#xff1a;巨大的印刷电路板 Chipset&#xff1a;芯片组&#xff0c;位于散热器下方&#xff0c;直接连接到CPU的系统代理部分 …

应急响应-网站入侵篡改指南Webshell内存马查杀漏洞排查时间分析

知识点 网站入侵篡改防范应对指南 主要需了解&#xff1a;异常特征&#xff0c;处置流程&#xff0c;分析报告等 主要需了解&#xff1a;日志存储&#xff0c;Webshell检测&#xff0c;分析思路等掌握 中间件日志存储&#xff0c;日志格式内容介绍&#xff08;IP,UA头,访问方…

KV260 BOOT.BIN更新 ubuntu22.04 netplan修改IP

KV260 2022.2设置 BOOT.BIN升级 KV260开发板需要先更新BOOT.BIN到2022.2版本&#xff0c;命令如下&#xff1a; sudo xmutil bootfw_update -i “BOOT-k26-starter-kit-202305_2022.2.bin” 注意BOOT.BIN应包含全目录。下面是更新到2022.1 FW的示例&#xff0c;非更新到2022.…

IPSec VPN

IP Security,IP安全 1、特点 L3的VPN 缺:不支持组播、配置复杂、延迟增加、资源消耗较多 优:具备访问控制、密码学四个维度、抗重放打击 2、组件 ①安全协议 1)验证头技术(AH) IP协议号51 提供数据完整性检查,身份验证,抗重放攻击 无法做数据的机密性 AH的完…

【异常错误】 Expected to have finished reduction in the prior iteration before star、find_unused_parameters

运行代码时出现了错误&#xff1a; RuntimeError: Expected to have finished reduction in the prior iteration before starting a new one. This error indicates that your module has parameters that were not used in producing loss. You can enable unused parameter …

【Django学习笔记(四)】JavaScript 语言介绍

JavaScript 语言介绍 前言正文1、JavaScript 小案例2、代码位置2.1 在当前 HTML 文件中2.2 在其他 js 文件中 3、代码注释3.1 HTML的注释3.2 CSS的注释3.3 Javascript的注释 4、变量 & 输出4.1 字符串4.2 数组4.3 对象(python里的字典) 5、条件语句6、函数7、DOM7.1 根据 I…

【树上倍增】【内向基环树】【 图论 】2836. 在传球游戏中最大化函数值

本文涉及知识点 树上倍增 内向基环树 图论 LeetCode2836. 在传球游戏中最大化函数值 给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。 总共有 n 名玩家&#xff0c;玩家 编号 互不相同&#xff0c;且为 [0, n - 1] 中的整数。这些玩家玩一个传球游戏&am…

ideaSSM图书借阅管理系统VS开发mysql数据库web结构java编程计算机网页源码maven项目

一、源码特点 SSM 图书借阅管理系统是一套完善的信息管理系统&#xff0c;结合SSM框架和bootstrap完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码 和数据库&#xff0c;系统主…

【爬虫+数据清洗+数据分析+可视化】“淄博烧烤”现象热评舆情python数据分析大屏

一、开发背景 您好&#xff0c;我是马哥小迷弟132 &#xff0c;一枚10年程序猿。 自从2023.3月以来&#xff0c;"淄博烧烤"现象持续占领热搜流量&#xff0c;体现了后疫情时代众多网友对人间烟火气的美好向往&#xff0c;本现象级事件存在一定的数据分析实践意义。…

Java零基础入门-java8新特性(上篇)

一、本期教学目标 java8有哪些新特性什么是函数式接口什么是Lambda表达式掌握Stream ApiStream和Collect集合区别Stream创建方式Stream操作三步骤 二、概述 上几期&#xff0c;我们是完整的学完了java异常类的学习及实战演示、以及学习了线程进程等基础概念&#xff0c;而这一…

Cache多核之间的一致性MESI

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 思考: 1、为什么要学习MESI协议&#xff1f; 哪里用到了&#xff1f;你确定真的用到了&#xff1f; 2、MESI只是一个协议&#xff0c;总得依赖一个硬件去执行该协议吧&#xff0c…