LeetCode 1245. 树的直径

Categories:

题目描述
思路分析
1. 解法一：两次 BFS（推荐）
相似题目

题目描述

✅ 1245. 树的直径

思路分析

解法一：两次 BFS（推荐）

核心思路：

从任意节点出发 BFS 找到最远节点 A。

从 A 再次 BFS，得到最远距离即为树的直径。

适用于无权树。

复杂度分析：

时间复杂度：O(n)，其中 n 表示节点数。

空间复杂度：O(n)，用于邻接表与队列。

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

class Solution {
    public int treeDiameter(int[][] edges) {
        int n = edges.length + 1;
        List<Integer>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] e : edges) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        int[] first = bfs(0, graph);
        int[] second = bfs(first[0], graph);
        return second[1];
    }

    private int[] bfs(int start, List<Integer>[] graph) {
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        visited[start] = true;

        int farthest = start;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            farthest = node;
            for (int next : graph[node]) {
                if (!visited[next]) {
                    visited[next] = true;
                    dist[next] = dist[node] + 1;
                    queue.offer(next);
                }
            }
        }

        return new int[]{farthest, dist[farthest]};
    }
}

func treeDiameter(edges [][]int) int {
	n := len(edges) + 1
	graph := make([][]int, n)
	for _, e := range edges {
		u, v := e[0], e[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	start, _ := bfsTree(0, graph)
	_, dist := bfsTree(start, graph)
	return dist
}

func bfsTree(start int, graph [][]int) (int, int) {
	n := len(graph)
	queue := make([]int, 0)
	queue = append(queue, start)
	visited := make([]bool, n)
	visited[start] = true
	dist := make([]int, n)

	farthest := start
	for head := 0; head < len(queue); head++ {
		node := queue[head]
		farthest = node
		for _, next := range graph[node] {
			if !visited[next] {
				visited[next] = true
				dist[next] = dist[node] + 1
				queue = append(queue, next)
			}
		}
	}

	return farthest, dist[farthest]
}

相似题目

题目	难度	考察点
543. 二叉树的直径	简单	DFS
310. 最小高度树	中等	BFS
834. 树中距离之和	困难	树形 DP
863. 二叉树中所有距离为 K 的结点	中等	BFS
1245. 树的直径	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/68665120