LeetoCode地址: . - 力扣(LeetCode)
可以通过归纳法证明出一棵树的最小高度树可以通过从最外面度为1的叶子节点一层一层向内遍历得到,可以使用一种称为 **中心缩减法**(或称为 **剥洋葱法**)的方法。我们将逐步解释这个方法,并证明其正确性。
### 定义和问题陈述
- **树**:无环连通图。
- **树的高度**:从根节点到任意叶子节点的最长路径。
- **最小高度树**:使树的高度最小的树。对于给定的无向树,可能存在多个根节点,使得树的高度最小。
### 中心缩减法(剥洋葱法)
这个方法的核心思想是逐步移除树的叶子节点(度为1的节点),直到剩下最后一个或两个节点,这些节点就是树的最小高度树的根。
### 证明
#### 步骤和直观理解
1. **初始阶段**:
- 考虑一棵树
2. **移除叶子节点**:
- 移除所有的叶子节点
- 移除叶子节点后,新的叶子节点是那些在
3. **重复过程**:
- 对于新的子树
- 这一过程持续进行,直到剩下一个或两个节点为止。
#### 数学证明
- **基础情况**:单节点树显然是其自身的最小高度树。
- **归纳步骤**:
- 设在移除了一层叶子节点后,新的子树
- 继续移除,直到树的高度不能再减少,这时剩下的一个或两个节点即为树的中心节点。
#### 详细证明
1. **叶子节点的性质**:
- 叶子节点位于树的最外层,其高度为最大高度。
- 移除叶子节点不会影响其他节点的连接性,因为树是无环连通图,移除叶子节点后剩下的子图依然是一棵树。
2. **递归缩减的效果**:
- 移除一层叶子节点后,新的子树
- 如果继续移除叶子节点,最终会缩减到树的中心部分。
3. **树的中心性质**:
- 对于树的最小高度树,其根节点到所有叶子节点的路径是最短的。
- 逐层移除叶子节点的方法保证了树的中心在最后一步被识别出来,因为剩下的一个或两个节点即为树的中心。
### 结论
通过逐层移除树的叶子节点,最终剩下的一个或两个节点即为树的中心节点,这些节点就是形成最小高度树的根节点。因此,树的最小高度树可以通过从最外面度为1的叶子节点一层一层向内遍历得到。
时间复杂度: O(n)
空间复杂度: O(n)
每一层‘洋葱皮’其实就是树的叶子结点集合,而每一层都是潜在的答案,所以我们要将其缓存起来,直到最后没有其他更内部的洋葱皮!。
- class Solution {
- public List<Integer> findMinHeightTrees(int n, int[][] edges) {
- List<Integer> res = new ArrayList<>();
- if (n == 1) {
- res.add(0);
- return res;
- }
-
- int[] degree = new int[n];
- ArrayList[] adj = new ArrayList[n];
- for (int i = 0; i < n; i++) {
- adj[i] = new ArrayList<Integer>();
- }
- for (int i = 0; i < edges.length; i++) {
- int x = edges[i][0], y = edges[i][1];
- degree[x]++;
- degree[y]++;
- adj[x].add(y);
- adj[y].add(x);
- }
-
- Deque<Integer> queue = new ArrayDeque<>();
- for (int i = 0; i < n; i++) {
- if (degree[i] == 1) {
- queue.offer(i);
- }
- }
-
- int remainCnt = n;
- while (remainCnt > 2) {
- int size = queue.size();
- remainCnt -= size;
- for (int i = 0; i < size; i++) {
- int u = queue.poll();
- List<Integer> nodes = adj[u];
- for (Integer next : nodes) {
- degree[next]--;
- if (degree[next] == 1) {
- queue.offer(next);
- }
- }
- }
- }
-
- while (!queue.isEmpty()) {
- res.add(queue.poll());
- }
- return res;
- }
- }