当前位置:网站首页>在最长的距离二叉树结点
在最长的距离二叉树结点
2022-07-06 12:57:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
分为两:①当后最长的距离root
②没有距离最长root,
1. 若路径经过根Root。则U和V是属于不同子树的,且它们都是该子树中道根节点最远的节点。否则跟它们的距离最远相矛盾。这样的情况如图3-13所看到的:
2. 假设路径不经过Root。那么它们一定属于根的K个子树之中的一个。
而且它们也是该子树中相距最远的两个顶点。如图3-14中的节点A:
设第K棵子树中相距最远的两个节点:Uk和Vk,其距离定义为d(Uk,Vk),那么节点Uk或Vk即为子树K到根节点Rk距离最长的节点。不失一般性。我们设Uk为子树K中道根节点Rk距离最长的节点。其到根节点的距离定义为d(Uk,R)。取d(Ui,R)(1<=i<=k)中最大的两个值max1和max2。那么经过根节点R的最长路径为max1+max2+2,所以树R中相距最远的两个点的距离为:max{d(U1,V1),…, d(Uk,Vk),max1+max2+2}。
採用深度优先搜索如图3-15,仅仅须要遍历全部的节点一次,时间复杂度为O(|E|)=O(|V|-1),当中V为点的集合。E为边的集合。
版权声明:本文博主原创文章。博客,未经同意不得转载。
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/117115.html原文链接:https://javaforall.cn
边栏推荐
- MLP (multilayer perceptron neural network) is a multilayer fully connected neural network model.
- Web开发小妙招:巧用ThreadLocal规避层层传值
- 3D face reconstruction: from basic knowledge to recognition / reconstruction methods!
- Aike AI frontier promotion (7.6)
- #yyds干货盘点#重新梳理箭头函数的this
- JS traversal array and string
- None of the strongest kings in the monitoring industry!
- Redis insert data garbled solution
- R語言可視化兩個以上的分類(類別)變量之間的關系、使用vcd包中的Mosaic函數創建馬賽克圖( Mosaic plots)、分別可視化兩個、三個、四個分類變量的關系的馬賽克圖
- 防火墙基础之外网服务器区部署和双机热备
猜你喜欢
基于STM32单片机设计的红外测温仪(带人脸检测)
What is the problem with the SQL group by statement
Introduction to the use of SAP Fiori application index tool and SAP Fiori tools
LLVM之父Chris Lattner:为什么我们要重建AI基础设施软件
Deployment of external server area and dual machine hot standby of firewall Foundation
Laravel笔记-自定义登录中新增登录5次失败锁账户功能(提高系统安全性)
##无yum源安装spug监控
性能测试过程和计划
面试官:Redis中有序集合的内部实现方式是什么?
【力扣刷题】32. 最长有效括号
随机推荐
The biggest pain point of traffic management - the resource utilization rate cannot go up
document.write()的用法-写入文本——修改样式、位置控制
Redis insert data garbled solution
[MySQL] trigger
【mysql】触发器
Regular expression collection
通过数字电视通过宽带网络取代互联网电视机顶盒应用
PG basics -- Logical Structure Management (transaction)
Swagger UI教程 API 文档神器
Comprehensive evaluation and recommendation of the most comprehensive knowledge base management tools in the whole network: flowus, baklib, jiandaoyun, ones wiki, pingcode, seed, mebox, Yifang cloud,
Reviewer dis's whole research direction is not just reviewing my manuscript. What should I do?
SAP Fiori应用索引大全工具和 SAP Fiori Tools 的使用介绍
Deployment of external server area and dual machine hot standby of firewall Foundation
C # use Oracle stored procedure to obtain result set instance
Common English vocabulary that every programmer must master (recommended Collection)
JS get array subscript through array content
Pinduoduo lost the lawsuit, and the case of bargain price difference of 0.9% was sentenced; Wechat internal test, the same mobile phone number can register two account functions; 2022 fields Awards an
Huawei device command
正则表达式收集
#yyds干货盘点#重新梳理箭头函数的this