求无向树中同值节点构成的最长路径（谷歌面试题）

Hey there! Let's work through this tricky Google interview problem together—tree problems with same-label path requirements are super common but easy to get tripped up on if you don't break them down right.

First off, let's fill in the missing piece about the E array since the problem description cut off. In most tree problems like this, E is the edge list: it's length 2*(N-1) because each undirected edge is stored twice, and for each pair E[2i] and E[2i+1], those are the two nodes connected by that edge (remember nodes are numbered 1 to N, so these values are 1-based node IDs).

Our goal is to find the longest path in the tree where every node has the same label. Typically, path length is counted as the number of edges (so a path with 3 nodes has length 2), but we'll note how to adjust if you need node count instead.

解题思路：深度优先搜索（DFS） #

Tree path problems almost always call for DFS, and this one is no exception. Here's the core idea:
For every node, we'll calculate two things:

1. The longest same-label path starting at this node and extending downward to its children.
2. The longest same-label path that passes through this node (connecting two of its child paths), which will help us track the global maximum.

Step-by-step breakdown: #

1. Build an adjacency list: Convert the edge array E into a structure that lets us easily traverse each node's neighbors. Since it's an undirected tree, each edge gets added to both nodes' neighbor lists.
2. Track the global maximum: Initialize a variable to keep track of the longest same-label path we've found so far.
3. DFS traversal: For each node:
   • Skip back to the parent node to avoid cycles.
   • For each child, recursively get the longest same-label path starting at that child.
   • If the child has the same label as the current node, update the two longest valid child paths we've seen (we need two because combining them through the current node gives a longer cross-path).
   • Update the global maximum with the longest path that passes through the current node (sum of the two longest child paths).
   • Return the longest single path starting at the current node to pass up to its parent.

代码示例（Python） #

def longest_same_label_path(A, E):
    node_count = len(A)
    if node_count == 0:
        return 0
    
    # Build adjacency list (nodes are 1-based)
    adjacency = [[] for _ in range(node_count + 1)]
    for i in range(0, len(E), 2):
        u = E[i]
        v = E[i+1]
        adjacency[u].append(v)
        adjacency[v].append(u)
    
    max_edge_length = 0  # Tracks longest path in terms of edges

    def dfs(current_node, parent_node):
        nonlocal max_edge_length
        current_label = A[current_node - 1]
        # Track top two longest same-label paths from children
        first_longest = 0
        second_longest = 0

        for neighbor in adjacency[current_node]:
            if neighbor == parent_node:
                continue
            child_path_length = dfs(neighbor, current_node)
            # Only consider paths where child has same label as current node
            if A[neighbor - 1] == current_label:
                if child_path_length + 1 > first_longest:
                    second_longest = first_longest
                    first_longest = child_path_length + 1
                elif child_path_length + 1 > second_longest:
                    second_longest = child_path_length + 1
        
        # Update global max: path through current node connecting two child paths
        current_max = first_longest + second_longest
        if current_max > max_edge_length:
            max_edge_length = current_max
        
        # Return longest single path starting at current node to parent
        return first_longest

    # Start DFS from any node (we'll use node 1 here)
    dfs(1, -1)
    # If you need path length in terms of nodes instead of edges, return max_edge_length + 1
    return max_edge_length

关键说明 #

• Time complexity: O(N) — every node is visited exactly once, and we iterate through each edge twice (once for each node), so it's linear time, which is optimal for tree problems.
• Space complexity: O(N) — mostly from the adjacency list and the recursion stack. For skewed trees (like a linked list), the recursion stack will be O(N); if you're worried about stack overflow, you can rewrite this with an iterative DFS.
• Node count vs edge count: If the problem asks for the number of nodes in the path instead of edges, just return max_edge_length + 1 (since edge count = node count - 1).

内容的提问来源于stack exchange，提问作者GettingPractice