美团笔试第一题
思路：
N个节点N-1条边的连通图一定是树，不存在环路，
所以根节点如果有多个子树，遍历完一个子树之后必须回到根节点才能进入其它子树，
只有最后一个子树不必返回，所以应该把最长的子树放在最后访问
递归表达式为：
dfs(start) = sum(dfs(i)+2) - depth
其中i表示第i个子树，最后一个子树不必返回，所以减去树的高度
import java.util.Scanner;
public class Meituan1 {
static int N;
static int[][] mat;
static boolean[] flag; //标记节点是否已访问过
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
mat = new int[N][N];
int n = N;
while (n-- > 1) {
int i = sc.nextInt();
int j = sc.nextInt();
mat[i - 1][j - 1] = mat[j - 1][i - 1] = 1;
}
flag = new boolean[N];
int maxDepth = depth(0);
flag = new boolean[N];
System.out.println(dfs(0) - maxDepth);
sc.close();
}
//递归求解访问所有子树并返回的路径总和
static int dfs(int start) {
flag[start] = true;
int res = 0;
for (int i = 0; i < N; i++) {
if (i != start && mat[start][i] != 0 && !flag[i]) {
res += 2 + dfs(i);
}
}
return res;
}
//递归求解树的高度
static int depth(int start) {
flag[start] = true;
int res = 0;
for (int i = 0; i < N; i++) {
if (i != start && mat[start][i] != 0 && !flag[i]) {
int idepth = 1 + depth(i);
if (idepth > res) res = idepth;
}
}
return res;
}
}
然而只过了9%。。。求大佬指正。。
查看12道真题和解析