1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
    public int treeDiameter(int[][] edges) {
        if (edges.length == 0) {
            return 0;
        }
        Map<Integer, Set<Integer>> nodeChildren = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildren.putIfAbsent(edge[0], new HashSet<>());
            nodeChildren.get(edge[0]).add(edge[1]);
            nodeChildren.putIfAbsent(edge[1], new HashSet<>());
            nodeChildren.get(edge[1]).add(edge[0]);
        }
        Deque<Integer> freeNodes = new ArrayDeque<>();
        for (Map.Entry<Integer, Set<Integer>> entry : nodeChildren.entrySet()) {
            if (entry.getValue().size() == 1) {
                freeNodes.add(entry.getKey());
            }
        }
        int count = 0;
        int lastTimeRemaining = 0;
        while (!freeNodes.isEmpty()) {
            int size = freeNodes.size();
            for (int i = 0; i < size; i++) {
                int currNode = freeNodes.pollFirst();
                Set<Integer> children = nodeChildren.get(currNode);
                for (Integer child : children) {
                    nodeChildren.get(child).remove(currNode);
                    if (nodeChildren.get(child).size() == 1) {
                        freeNodes.offerLast(child);
                    }
                }
            }
            lastTimeRemaining = size;
            count += 1;
        }
        return lastTimeRemaining == 1 ? 2 * count - 2 : 2 * count - 1;
    }
}

/**
 * topological sort.
 * 
 * count数的是一共减了几圈. 我们需要统计最后一圈去掉了几个nodes. 如果去掉了两个, 那么最长的chain就是圈数 * 2, 如果最后只去掉了一个
 * 那就是(圈数 - 1) * 2 + 1.
 * 
 * 除了最后一圈, 每一圈一定是去掉2个极其以上的nodes的.
 * 
 * 时间复杂度: O(n)
 * 空间复杂度: O(n) 用了map以及queue.
 */

class Solution {
    private int ans = 0;

    public int treeDiameter(int[][] edges) {
        if (edges.length == 0) {
            return 0;
        }
        Map<Integer, Set<Integer>> nodeChildren = new HashMap<>();
        for (int[] edge : edges) {
            nodeChildren.putIfAbsent(edge[0], new HashSet<>());
            nodeChildren.get(edge[0]).add(edge[1]);
            nodeChildren.putIfAbsent(edge[1], new HashSet<>());
            nodeChildren.get(edge[1]).add(edge[0]);
        }
        getHeight(edges[0][0], -1, nodeChildren);
        return ans;
    }

    private int getHeight(int node, int parent, Map<Integer, Set<Integer>> nodeChildren) {
        int maxHeight = 0;
        for (int child : nodeChildren.get(node)) {
            if (child == parent) {
                continue;
            }
            int currHeight = getHeight(child, node, nodeChildren);
            ans = Math.max(ans, currHeight + maxHeight);
            maxHeight = Math.max(maxHeight, currHeight);
        }
        return maxHeight + 1;
    }
}

正常dfs去解决. 还是定义递归函数告诉我们某个tree的height是多少. 这里我们不需要记录最大的两个height, 只记录最大的即可. 我们每次得到currHeight的时候都和maxHeight配对然后跟ans比较即可. 然后及时更新maxHeight.

注意不要往parent方向走, 因此我们多传入了一个parent这个参数.

这里map中的value其实不必非要用set, 用list也行. 只是这里用map存每个node的children是第一种解法复制过来的, 我懒得改. 甚至都不用使用map, 因为node是从0到n - 1, 因此用个list就行, 下标对应每个node的children情况.

时间复杂度: O(n)
空间复杂度: O(n)