难度: Medium
Submission
运行时间: 43 ms
内存: 20.2 MB
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
# find the deepest and second deepest subpath
g = collections.defaultdict(list)
for u, v in edges:
g[u].append(v)
g[v].append(u)
def bfs(start):
seen = set()
seen.add(start)
queue = deque([start])
distance = -1
last_node = None
while queue:
length = len(queue)
for i in range(length):
next_node = queue.popleft()
for neighbor in g[next_node]:
if neighbor not in seen:
seen.add(neighbor)
queue.append(neighbor)
last_node = neighbor
distance += 1
return last_node, distance
farthest_node, d1 = bfs(0)
another_farthest_node, d2 = bfs(farthest_node)
return d2
Explain
该题解利用了广度优先搜索（BFS）算法来计算无向树的直径。解题思路包括：1) 构建无向图的邻接表表示。2) 从任意一个结点（这里选择了结点0）开始进行一次BFS，找到距离这个结点最远的结点，记为farthest_node。3) 从farthest_node再进行一次BFS，找到从这个点出发能到达的最远距离，即为树的直径。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
# Initialize graph as an adjacency list
g = collections.defaultdict(list)
# Build the graph from the list of edges
for u, v in edges:
g[u].append(v)
g[v].append(u)
# Perform BFS to find the farthest node and its distance from the start node
def bfs(start):
seen = set() # Track visited nodes
seen.add(start)
queue = deque([start]) # Queue for BFS
distance = -1 # Initialize distance
last_node = None # Track the last node visited in the current BFS layer
while queue:
length = len(queue) # Number of nodes at the current BFS level
for i in range(length):
next_node = queue.popleft() # Dequeue the next node
for neighbor in g[next_node]: # Check all adjacent nodes
if neighbor not in seen: # If not visited
seen.add(neighbor) # Mark as visited
queue.append(neighbor) # Enqueue for further BFS
last_node = neighbor # Update last node visited
distance += 1 # Increment distance for each level of BFS
return last_node, distance
farthest_node, d1 = bfs(0) # First BFS from an arbitrary start node (node 0)
another_farthest_node, d2 = bfs(farthest_node) # Second BFS from the farthest node found
return d2 # Return the diameter of the tree, which is the distance in the second BFS
Explore
在无向树中，从任意节点开始的第一次BFS能找到最远的节点，是因为树是一个连通且无环的特殊图结构，任意两点间有且仅有一条路径。进行一次BFS会遍历所有节点，并最终到达某个叶节点。由于任意节点到叶节点的路径可能是最长路径的一部分，所以第一次BFS能确保找到一个端点。选择不同的起始节点，最终找到的最远节点可能不同，但这不影响第二次BFS找到的树的直径长度，因为树的直径是定义为任意两点间的最长距离，而这两点必定是树叶。
这种方法在所有类型的树结构中都有效。无论树的形态如何（包括非常不平衡的树），树的直径都是从一个叶节点到另一个叶节点的最长路径。通过从任一节点找到的最远节点（必然是一个叶节点）开始第二次BFS，可以保证无论树的形态如何，都能找到另一个最远的叶节点，从而正确计算出树的直径。
选择邻接表而不是邻接矩阵的主要原因是空间效率。树中的节点数与边数几乎相等（N个节点有N-1条边），使用邻接矩阵表示会创建一个N×N的矩阵，大多数位置为空，导致空间浪费。而邻接表只存储每个节点的直接邻居，空间复杂度是O(N)，更适合稀疏图，如树。此外，使用邻接表可以更快地迭代节点的邻居，提高算法效率。
使用队列和已访问节点集合是BFS的标准实现，以确保每个节点仅被访问一次，避免重复访问造成无限循环。这种方法在大多数情况下已经是最优的，特别是在处理树这种没有环的结构时。然而，对于特定类型的数据或环境，可以考虑一些优化措施，例如使用更快的队列实现（如双端队列），或在内存使用上进行优化（例如使用位向量来标记已访问的节点）。在多核或并行环境下，可以考虑并行BFS算法以进一步提高效率。