求解Leetcode Minimum Height Trees问题：递归实现遇阻求助

Hey there! Let's break down what's missing in your current code for the Minimum Height Trees problem. I see you're trying to use a recursive approach with color marking to calculate tree heights, but you're stuck on how to track and compare those heights to find the minimum ones.

What's Missing in Your Current Code #

Right now, your calculateHeight function only traverses nodes (marking them Grey/White) but doesn't actually compute the height of the tree when rooted at a given node. You also aren't comparing these heights to find the minimums, or adding the correct starting nodes to your result list.

Fixing the Approach #

Here's how to adjust your code to make it work:

• Modify calculateHeight to return the actual height of the tree rooted at the current node. The height of a node is 1 plus the maximum height of all its child subtrees.
• Track the minimum height across all starting nodes in your main loop: update the result list whenever you find a smaller height (clear the list and add the new node) or an equal height (add the node to the list).
• Avoid revisiting the parent node (since the graph is undirected) — combining a parent parameter with your color marking keeps the logic clean.

Updated Code #

import java.util.*;

class Solution {
    enum Color { White, Grey; }

    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int minHeight = Integer.MAX_VALUE;
        List<List<Integer>> adjLists = buildGraph(n, edges);
        List<Integer> ret = new ArrayList<>();
        Color[] visited = new Color[n];

        for (int i = 0; i < n; i++) {
            // Reset visited array for each new starting node
            Arrays.fill(visited, Color.White);
            // Calculate height when tree is rooted at i
            int currentHeight = calculateHeight(adjLists, i, -1, visited);
            
            // Update result based on current height
            if (currentHeight < minHeight) {
                minHeight = currentHeight;
                ret.clear();
                ret.add(i);
            } else if (currentHeight == minHeight) {
                ret.add(i);
            }
        }
        return ret;
    }

    private List<List<Integer>> buildGraph(int n, int[][] edges) {
        List<List<Integer>> adjLists = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjLists.add(new ArrayList<>());
        }
        for (int[] node : edges) {
            int v = node[0], u = node[1];
            adjLists.get(u).add(v);
            adjLists.get(v).add(u);
        }
        return adjLists;
    }

    private int calculateHeight(List<List<Integer>> adjLists, int start, int parent, Color[] visited) {
        visited[start] = Color.Grey;
        int maxChildHeight = 0;

        // Iterate through all neighbors
        for (int neighbor : adjLists.get(start)) {
            // Skip parent node and already visited nodes
            if (neighbor != parent && visited[neighbor] == Color.White) {
                int childHeight = calculateHeight(adjLists, neighbor, start, visited);
                maxChildHeight = Math.max(maxChildHeight, childHeight);
            }
        }

        // Backtrack: unmark the node as visited for other traversals
        visited[start] = Color.White;
        // Height of current node is 1 (itself) plus the tallest child subtree
        return maxChildHeight + 1;
    }
}

Key Notes #

• Height Calculation: The calculateHeight function now returns the height of the tree rooted at start by recursively finding the tallest child subtree and adding 1 (for the current node).
• Result Updates: In the main loop, we reset the visited array for each starting node, compute its tree height, and adjust the result list based on whether this height is smaller than, equal to, or larger than the current minimum.
• Efficiency Note: This recursive approach has a time complexity of O(n²), which might time out for large values of n (like n=10^4). For a more efficient solution, you can use a topological sorting approach (removing leaf nodes iteratively until 1 or 2 nodes remain — those are the MHT roots). But this adjusted code will work correctly for smaller test cases and helps you nail down the recursive logic first.

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