题解 | #求树的根#
求树的根
https://www.nowcoder.com/practice/e5a97317b37d46dcb10dd5dce66a2ec4
题目链接
题目描述
给定一棵包含 个节点的有根树，节点编号从 1 到
。输入以
条有向边
u -> v 的形式给出。你需要找出并输出：
- 树的根节点编号。
- 所有叶子节点的编号，并按升序排列。
解题思路
这道题的本质是利用图论中节点度 (degree) 的概念来识别树的特定部分。题目以有向边的形式给出了树的结构，这为我们提供了清晰的方向。
核心定义
- 入度 (In-degree)：指向一个节点的边的数量。
- 出度 (Out-degree)：从一个节点出发的边的数量。
根据有根树的性质，我们可以得出以下结论：
- 根节点：是树的唯一源头，没有其他节点指向它。因此，根节点的入度为 0。
- 叶子节点：是树的末端，不再指向任何其他节点。因此，叶子节点的出度为 0。
算法流程
-
初始化：创建两个数组，
in_degree和out_degree，大小都为，并全部初始化为 0。它们将分别用于记录每个节点的入度和出度。
-
计算度数：遍历所有
条输入的边。对于每一条边
u -> v：- 节点
的出度加一，即
out_degree[u]++。 - 节点
的入度加一，即
in_degree[v]++。
- 节点
-
寻找根节点：遍历从 1 到
的所有节点。找到那个
in_degree值为 0 的节点，它就是唯一的根节点。 -
寻找叶子节点：遍历从 1 到
out_degree值为 0 的节点收集起来。由于我们是按节点编号从小到大进行遍历的，所以收集到的叶子节点列表自然就是升序的，无需额外排序。 -
输出结果：按题目格式要求，先输出根节点，再输出排序后的叶子节点列表。
代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
if (n == 1) {
cout << 1 << "\n" << 1 << "\n";
return 0;
}
vector<int> in_degree(n + 1, 0);
vector<int> out_degree(n + 1, 0);
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
out_degree[u]++;
in_degree[v]++;
}
int root = -1;
for (int i = 1; i <= n; ++i) {
if (in_degree[i] == 0) {
root = i;
break;
}
}
cout << root << "\n";
vector<int> leaves;
for (int i = 1; i <= n; ++i) {
if (out_degree[i] == 0) {
leaves.push_back(i);
}
}
for (int i = 0; i < leaves.size(); ++i) {
cout << leaves[i] << (i == leaves.size() - 1 ? "" : " ");
}
cout << "\n";
return 0;
}
import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n == 1) {
System.out.println(1);
System.out.println(1);
return;
}
int[] inDegree = new int[n + 1];
int[] outDegree = new int[n + 1];
for (int i = 0; i < n - 1; i++) {
int u = sc.nextInt();
int v = sc.nextInt();
outDegree[u]++;
inDegree[v]++;
}
int root = -1;
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
root = i;
break;
}
}
System.out.println(root);
List<Integer> leaves = new ArrayList<>();
for (int i = 1; i <= n; i++) {
if (outDegree[i] == 0) {
leaves.add(i);
}
}
for (int i = 0; i < leaves.size(); i++) {
System.out.print(leaves.get(i) + (i == leaves.size() - 1 ? "" : " "));
}
System.out.println();
}
}
import sys
def solve():
try:
n_str = sys.stdin.readline()
if not n_str: return
n = int(n_str)
if n == 1:
print(1)
print(1)
return
in_degree = [0] * (n + 1)
out_degree = [0] * (n + 1)
for _ in range(n - 1):
u, v = map(int, sys.stdin.readline().split())
out_degree[u] += 1
in_degree[v] += 1
root = -1
for i in range(1, n + 1):
if in_degree[i] == 0:
root = i
break
print(root)
leaves = []
for i in range(1, n + 1):
if out_degree[i] == 0:
leaves.append(i)
print(*leaves)
except (IOError, ValueError):
return
solve()
算法及复杂度
-
算法：计算节点的入度和出度。
-
时间复杂度：
。
- 读入
- 遍历所有节点一次以找到根节点，需要
- 再次遍历所有节点以找到所有叶子节点，需要
- 总体时间复杂度为
- 读入
-
空间复杂度：
- 需要两个大小为
- 需要两个大小为
