题意整理
- 给定一棵树,求出这棵树的直径,即树上最远两点的距离。
方法一(dfs)
1.解题思路
- 首先初始化邻接表,以边的起点为索引,将对应的边的终点以及边的权值放在该索引对应的list里。
- 先从0号节点进入递归,通过递归找到当前节点所能到达的最远节点,跟新最远节点的规则是路径权值和大于之前的权值和。
- 然后再从最远节点处继续进入递归体,寻找最大路径权值和。
动图展示:
2.代码实现
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* }
*/
public class Solution {
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类一维数组 树的边
* @param Edge_value int整型一维数组 边的权值
* @return int整型
*/
//邻接表
List<List<int[]>> graph;
//记录最远节点
long far=0;
//记录无重复最长路径,即树的直径
long max=0;
public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
//初始化邻接表
graph=new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
//以边的起点为索引,将对应的边的终点以及边的权值放在list里
for(int i=0;i<Tree_edge.length;i++){
graph.get(Tree_edge[i].start).add(new int[]{Tree_edge[i].end,Edge_value[i]});
graph.get(Tree_edge[i].end).add(new int[]{Tree_edge[i].start,Edge_value[i]});
}
//从0号节点开始递归
dfs(0,-1,0);
max=0;
//找到最远点后,从当前点递归
dfs(far,-1,0);
return (int)max;
}
//深度优先搜索
private void dfs(long cur,long pre,long dist){
//跟新当前最长路径以及最远点
if(dist>max){
max=dist;
far=cur;
}
for(int[] child:graph.get((int)cur)){
//如果没有走回头路,则沿子节点方向递归
if(child[0]!=(int)pre){
dfs(child[0],cur,dist+child[1]);
}
}
}
}
3.复杂度分析
- 时间复杂度:假设树中所有节点个数为n,需要遍历所有的节点,所以时间复杂度是。
- 空间复杂度:最坏情况下邻接表的大小为,所以空间复杂度为。
方法二(bfs)
1.解题思路
- 首先初始化邻接表,以边的起点为索引,将对应的边的终点以及边的权值放在该索引对应的list里。
- 将0号节点入队,找到当前节点所能到达的最远节点,跟新最远节点的规则是路径权值和大于之前的权值和。如果没有走回头路,将所有可能的子节点入队。
- 找到最远节点后,继续将最远节点入队,找出最大权值和。
2.代码实现
import java.util.*;
/*
* public class Interval {
* int start;
* int end;
* }
*/
public class Solution {
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类一维数组 树的边
* @param Edge_value int整型一维数组 边的权值
* @return int整型
*/
//邻接表
List<List<int[]>> graph;
//记录最远节点
long far=0;
//记录无重复最长路径
long max=0;
public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
//初始化邻接表
graph=new ArrayList<>();
for(int i=0;i<n;i++){
graph.add(new ArrayList<>());
}
//以边的起点为索引,将对应的边的终点以及边的权值放在list里
for(int i=0;i<Tree_edge.length;i++){
graph.get(Tree_edge[i].start).add(new int[]{Tree_edge[i].end,Edge_value[i]});
graph.get(Tree_edge[i].end).add(new int[]{Tree_edge[i].start,Edge_value[i]});
}
//初始化队列
Queue<long[] > queue=new LinkedList<>();
//从0号节点开始找
bfs(queue,0,-1,0);
max=0;
//找到最远点后,从当前点继续找
bfs(queue,far,-1,0);
return (int)max;
}
//广度优先搜索
private void bfs(Queue<long[] > queue,long cur,long pre,long dist){
//加入起始节点到队列
queue.offer(new long[]{cur,pre,dist});
while(!queue.isEmpty()){
//取出当前节点信息
long[] node=queue.poll();
cur=node[0];
pre=node[1];
dist=node[2];
//如果大于max,则跟新最远距离以及最远节点
if(dist>max){
max=dist;
far=cur;
}
for(int[] child:graph.get((int)cur)){
//如果没有走回头路,则将子节点放入队列
if(child[0]!=(int)pre){
queue.offer(new long[]{child[0],cur,dist+child[1]});
}
}
}
}
}
3.复杂度分析
- 时间复杂度:假设树中所有节点个数为n,需要遍历所有的节点,所以时间复杂度是。
- 空间复杂度:最坏情况下邻接表的大小为,所以空间复杂度为。