-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy patharticle-40587.htm
205 lines (193 loc) · 17.9 KB
/
article-40587.htm
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
<!DOCTYPE html>
<html xml:lang="zh-CN" lang="zh-CN">
<head>
<link rel="canonical" href="https://windowsv2ray.github.io/news/article-40587.htm" />
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<title>Java实现最小高度树_java</title>
<meta name="description" content="目录 题设要求 示例 1： 示例 2： 解题思路 算法 题设要求 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个" />
<link rel="icon" href="/assets/website/img/windowsv2ray/favicon.ico" type="image/x-icon"/>
<meta name="author" content="Windows V2ray分享订阅站">
<meta property="og:type" content="article" />
<meta property="og:url" content="https://windowsv2ray.github.io/news/article-40587.htm" />
<meta property="og:site_name" content="Windows V2ray分享订阅站" />
<meta property="og:title" content="Java实现最小高度树_java" />
<meta property="og:image" content="https://windowsv2ray.github.io/uploads/20240604/7c9b9478eede1a06f8e9fbcc9f165e66.webp" />
<meta property="og:release_date" content="2025-01-14T07:35:38" />
<meta property="og:updated_time" content="2025-01-14T07:35:38" />
<meta property="og:description" content="目录 题设要求 示例 1： 示例 2： 解题思路 算法 题设要求 树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。 给你一棵包含 n 个" />
<meta name="applicable-device" content="pc,mobile" />
<meta name="renderer" content="webkit" />
<meta name="force-rendering" content="webkit" />
<meta http-equiv="Cache-Control" content="no-transform" />
<meta name="robots" content="max-image-preview:large" />
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="apple-mobile-web-app-title" content="Java实现最小高度树_java">
<meta name="format-detection" content="telephone=no">
<link rel="dns-prefetch" href="https:/www.googletagmanager.com">
<link rel="dns-prefetch" href="https://www.googleadservices.com">
<link rel="dns-prefetch" href="https://www.google-analytics.com">
<link rel="dns-prefetch" href="https://pagead2.googlesyndication.com">
<link rel="dns-prefetch" href="https://cm.g.doubleclick.net">
<link rel="stylesheet" href="/assets/website/js/frontend/windowsv2ray/animate/animate.css">
<link rel="stylesheet" href="/assets/website/css/windowsv2ray/bootstrap.css">
<link rel="stylesheet" href="/assets/website/css/windowsv2ray/maicons.css">
<link rel="stylesheet" href="/assets/website/js/frontend/windowsv2ray/owl-carousel/css/owl.carousel.css">
<link rel="stylesheet" href="/assets/website/css/windowsv2ray/theme.css">
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-JN82W0GJX5"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-JN82W0GJX5');
</script>
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-3332997411212854"
crossorigin="anonymous"></script>
</head>
<body data-page="detail">
<!-- Back to top button -->
<div class="back-to-top"></div>
<header>
<nav class="navbar navbar-expand-lg navbar-light navbar-float">
<div class="container">
<a href="/" class="navbar-brand">
<span>Windows V2ray</span>
</a>
<button class="navbar-toggler" data-toggle="collapse" data-target="#navbarContent" aria-controls="navbarContent" aria-expanded="false" aria-label="Toggle navigation">
<span class="navbar-toggler-icon"></span>
</button>
<div class="navbar-collapse collapse" id="navbarContent">
<ul class="navbar-nav ml-lg-4 pt-3 pt-lg-0">
<li class="nav-item">
<a href="/" class="nav-link">首页</a>
</li>
<li class="nav-item">
<a href="/free-nodes/" class="nav-link">免费节点</a>
</li>
<li class="nav-item">
<a href="/paid-subscribe/" class="nav-link">推荐机场</a>
</li>
<li class="nav-item">
<a href="/client.htm" class="nav-link">客户端</a>
</li>
<li class="nav-item">
<a href="/news/" class="nav-link">新闻资讯</a>
</li>
</ul>
</div>
</div>
</nav>
<div class="container mt-5">
<div class="page-banner">
<div class="row justify-content-center align-items-center h-100">
<div class="col-md-10">
<h1 class="text-center">Java实现最小高度树_java</h1>
<nav aria-label="Breadcrumb">
<ul class="breadcrumb justify-content-center py-0 bg-transparent">
<li class="breadcrumb-item"><a href="/">首页</a></li>
<li class="breadcrumb-item"><a href="/news/">新闻资讯</a></li>
<li class="breadcrumb-item active">正文</li>
</ul>
</nav>
</div>
</div>
</div>
</div>
</header>
<main>
<div class="page-section">
<div class="container">
<div class="row">
<div class="col-md-9">
<input type="hidden" id="share-website-info" data-name="" data-url="">
<div id="navCategory"> <h5 class="catalogue">目录</h5> <ul class="first_class_ul"> <li><a href="#_label0" rel="nofollow">题设要求</a></li> <li><a href="#_label1" rel="nofollow">示例 1：</a></li> <li><a href="#_label2" rel="nofollow">示例 2：</a></li> <li><a href="#_label3" rel="nofollow">解题思路</a></li> <li><a href="#_label4" rel="nofollow">算法</a></li> </ul> </div> <p class="maodian"><a name="_label0" rel="nofollow"></a></p> <h2>题设要求</h2> <p>树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，一个任何没有简单环路的连通图都是一棵树。</p> <p>给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。</p> <p>可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。</p> <p>请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。</p> <p>树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。</p> <p class="maodian"><a name="_label1" rel="nofollow"></a></p> <h2>示例 1：</h2> <p style="text-align:center"><img decoding="async" alt="请添加图片描述" src="http://img.555519.xyz/uploads3/20220420/65062274d9146504a89184925e024ec9.jpg"></p> <p>输入：n = 4, edges = [[1,0],[1,2],[1,3]]<br />输出：[1]<br />解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。</p> <p class="maodian"><a name="_label2" rel="nofollow"></a></p> <h2>示例 2：</h2> <p><img decoding="async" alt="请添加图片描述" src="http://img.555519.xyz/uploads3/20220420/0f606631916f86383958c6d13315f262.jpg"></p> <blockquote> <p>输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]<br />输出：[3,4]</p> </blockquote> <blockquote> <p>提示：<br />1 <= n <= 2 * 104<br />edges.length == n - 1<br />0 <= ai, bi < n<br />ai != bi<br />所有 (ai, bi) 互不相同<br />给定的输入保证是一棵树，并且不会有重复的边</p> </blockquote> <p class="maodian"><a name="_label3" rel="nofollow"></a></p> <h2>解题思路</h2> <p> 由上述两个图我们可以得出结论：题中需要求解的是树里面的中心节点，而每个树的中心节点不会超过两个。</p> <p> 而我们想要求得树里面的中心节点，我们就可以逐层FBS（也就是逐层将出度为一的叶子节点剪掉），直至剪到最后一层，就可以将结果输出了！</p> <p class="maodian"><a name="_label4" rel="nofollow"></a></p> <h2>算法</h2> <div class="ay1code"> <pre class="brush:java;">class Solution { public List<Integer> findMinHeightTrees(int n, int[][] edges) { List<Integer> res = new ArrayList<Integer>(); //如果只有一个节点，则它就是最小高度树 if(n == 1){ res.add(0); return res; } //每个节点的邻居数量 int [] degree = new int[n]; //每个节点的邻居 HashMap<Integer,List<Integer>> map = new HashMap<>(); for(int [] edge : edges){ int a = edge[0]; int b = edge[1]; degree[a]++; degree[b]++; if(map.get(a) == null){ map.put(a,new ArrayList<Integer>());//key:节点 value:邻居 } if(map.get(b) == null){ map.put(b,new ArrayList<Integer>());//key:节点 value:邻居 } map.get(a).add(b); map.get(b).add(a); } //建立队列 LinkedList<Integer> leafNodes = new LinkedList<Integer>();//表示叶子节点 //将所有度为1的节点入队 for(int i = 0;i < degree.length;i++){ if(degree[i] == 1){ leafNodes.add(i); } } while(leafNodes.size() > 0){ res.clear(); //每一层节点的数量 int size = leafNodes.size(); for(int i = 0;i < size;i++){ int leaf = leafNodes.poll(); //将当前节点加入到结果集 res.add(leaf); List<Integer> neighbors = map.get(leaf); //将出度减一，也就是将最外层的叶子节点剪掉 for(int neighbor : neighbors){ degree[neighbor]--; if(degree[neighbor] == 1){ //叶子节点入队 leafNodes.add(neighbor); } } } } return res; } } </pre> </div> <div class="clearfix"></div>
<div class="col-md-12 mt-5">
<p>上一个：<a href="/news/article-40087.htm">宠物领养协议书怎么生效图片 宠物领养协议书怎么生效图片大全</a></p>
<p>下一个：<a href="/news/article-40588.htm">动物医院诊疗系统有哪些设备（动物医院诊疗程序）</a></p>
</div>
</div>
<div class="col-md-3">
<div class="panel panel-default">
<div class="panel-heading">
<h3 class="panel-title">热门文章</h3>
</div>
<div class="panel-body">
<ul class="p-0 x-0" style="list-style: none;margin: 0;padding: 0;">
<li class="py-2"><a href="/free-nodes/2025-1-22-free-shadowrocket-node.htm" title="「1月22日」最高速度21.3M/S，2025年V2ray/Clash/SSR/Shadowrocket每天更新免费节点订阅链接">「1月22日」最高速度21.3M/S，2025年V2ray/Clash/SSR/Shadowrocket每天更新免费节点订阅链接</a></li>
<li class="py-2"><a href="/news/article-62244.htm" title="动物疫苗研发生产流程图（动物疫苗研制步骤）">动物疫苗研发生产流程图（动物疫苗研制步骤）</a></li>
<li class="py-2"><a href="/free-nodes/2025-1-27-free-clash.htm" title="「1月27日」最高速度22.7M/S，2025年Shadowrocket/Clash/V2ray/SSR每天更新免费节点订阅链接">「1月27日」最高速度22.7M/S，2025年Shadowrocket/Clash/V2ray/SSR每天更新免费节点订阅链接</a></li>
<li class="py-2"><a href="/news/article-39115.htm" title="国考公务员报名2021（国考公务员报名入口）">国考公务员报名2021（国考公务员报名入口）</a></li>
<li class="py-2"><a href="/free-nodes/2025-2-19-clash-windows.htm" title="「2月19日」最高速度20.8M/S，2025年V2ray/Shadowrocket/SSR/Clash每天更新免费节点订阅链接">「2月19日」最高速度20.8M/S，2025年V2ray/Shadowrocket/SSR/Clash每天更新免费节点订阅链接</a></li>
<li class="py-2"><a href="/news/article-61068.htm" title="我所在的城市有一家动物医院的英文怎么写（在我的城市有一家宠物医院的英语怎么说）">我所在的城市有一家动物医院的英文怎么写（在我的城市有一家宠物医院的英语怎么说）</a></li>
<li class="py-2"><a href="/news/article-54826.htm" title="中国宠物食品行业十大质量品牌排行榜（国内宠物食品企业排名）">中国宠物食品行业十大质量品牌排行榜（国内宠物食品企业排名）</a></li>
<li class="py-2"><a href="/news/article-41069.htm" title="spring常用配置profile(设置不同的运行环境)使用纪要">spring常用配置profile(设置不同的运行环境)使用纪要</a></li>
<li class="py-2"><a href="/news/article-37623.htm" title="动物疫苗接种时间表图片高清（动物疫苗接种时间表图片高清大图）">动物疫苗接种时间表图片高清（动物疫苗接种时间表图片高清大图）</a></li>
<li class="py-2"><a href="/news/article-61655.htm" title="免费领养猫平台下载（免费领养猫平台下载什么软件）">免费领养猫平台下载（免费领养猫平台下载什么软件）</a></li>
</ul>
</div>
</div>
<div class="panel panel-default">
<div class="panel-heading">
<h3 class="panel-title">归纳</h3>
</div>
<div class="panel-body">
<ul class="p-0 x-0" style="list-style: none;margin: 0;padding: 0;">
<li class="py-2">
<h4><span class="badge" style="float: right;">12</span> <a href="/date/2025-03/" title="2025-03 归档">2025-03</a></h4>
</li>
<li class="py-2">
<h4><span class="badge" style="float: right;">84</span> <a href="/date/2025-02/" title="2025-02 归档">2025-02</a></h4>
</li>
<li class="py-2">
<h4><span class="badge" style="float: right;">83</span> <a href="/date/2025-01/" title="2025-01 归档">2025-01</a></h4>
</li>
</ul>
</div>
</div>
</div>
</div>
</div> <!-- .container -->
</div> <!-- .page-section -->
</main>
<footer class="page-footer">
<div class="container">
<div class="row">
<div class="col-sm-6 py-2">
<p id="copyright">
<p>
<a href="/">首页</a> |
<a href="/free-node/">免费节点</a> |
<a href="/news/">新闻资讯</a> |
<a href="/about-us.htm">关于我们</a> |
<a href="/disclaimer.htm">免责申明</a> |
<a href="/privacy.htm">隐私申明</a> |
<a href="/sitemap.xml">网站地图</a>
</p>
Windows V2ray分享订阅站 版权所有 Powered by WordPress
</p>
</div>
<div class="col-sm-6 py-2 text-right">
<div class="d-inline-block px-3">
<a href="#">Privacy</a>
</div>
<div class="d-inline-block px-3">
<a href="#">Contact Us</a>
</div>
</div>
</div>
</div> <!-- .container -->
</footer> <!-- .page-footer -->
<script src="/assets/website/js/frontend/windowsv2ray/jquery-3.5.1.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/bootstrap.bundle.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/wow/wow.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/owl-carousel/js/owl.carousel.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/waypoints/jquery.waypoints.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/animateNumber/jquery.animateNumber.min.js"></script>
<script src="/assets/website/js/frontend/windowsv2ray/theme.js"></script>
<script src="https://www.freeclashnode.com/assets/js/frontend/invite-url.js"></script>
<script src="/assets/website/js/frontend/G.js"></script>
</body>
</html>