LeetCode 310 Minimum Height Trees

Posted on | In | 阅读 
寻找以哪个节点作为根节点的时候树的高度最小。

  1. 作为根节点的节点一定在树的直径的中点。如果不在中点，那么一定有一个节点的距离根节点超过树的半径的距离。（树上路径唯一，直径连接两个叶子节点，那么如果根节点不在直径上，有一个节点至少需要走完半径后再走向根节点）

  2. 寻找直径的方法，两次bfs和分治法，以为这题需要得到路径所以我用的是两次bfs，第一次从任意一个点o出发找到离它最远的点p，第二次再从q出发找离它最远的点q，p-q就是直径。

    证明：如果p-q不是直径，那么假设直径为a-b

    1）a-b与o-p相交于m，由于p是距离o最远的点，所以om+mp > om+ma，mp>ma，b-p>a-b，与a-b直径矛盾

    2）a-b与o-p不相交，那么两条路径间通过m-n连通，om+mp > om+mn+nb，mp>mn+nb，an+mn+mp > an+mn+nb > ab 与a-b直径矛盾

  3. 分治法的话就是从叶子节点开始，计算节点距离叶子节点的距离，父节点的最大距离=max(子节点) + 1，树形dp。还需要缓存下第二大距离，最后最远距离+次远距离就是直径长。

C++ Code

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
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>> head(n);
        vector<int> f(n, -1);
        for(int i = 0; i < edges.size(); ++i) {
            head[edges[i][0]].push_back(edges[i][1]);
            head[edges[i][1]].push_back(edges[i][0]);
        }
        queue<pair<int, int>> q;
        q.push(make_pair(-1, 0));
        int last_node;
        while(!q.empty()) {
            int sz = q.size();
            for(int i = 0; i < sz; ++i) {
                pair<int, int> cur = q.front();
                q.pop();
                last_node = cur.second;
                int father = cur.first;
                for(int j = 0; j < head[last_node].size(); ++j) {
                    if(head[last_node][j] == father)
                        continue;
                    q.push(make_pair(last_node, head[last_node][j]));
                }
            }
        }
        
        int cur_node;
        q.push(make_pair(-1, last_node));
        while(!q.empty()) {
            int sz = q.size();
            for(int i = 0; i < sz; ++i) {
                pair<int, int> cur = q.front();
                q.pop();
                cur_node = cur.second;
                int father = cur.first;
                f[cur_node] = father;
                for(int j = 0; j < head[cur_node].size(); ++j) {
                    if(head[cur_node][j] == father)
                        continue;
                    q.push(make_pair(cur_node, head[cur_node][j]));
                }
            }
        }
        
        vector<int> path;
        while(cur_node != last_node) {
            path.push_back(cur_node);
            cur_node = f[cur_node];
        }
        path.push_back(last_node);
        vector<int> ans;
        if(path.size() % 2 == 1) {
            ans.push_back(path[path.size() / 2]);
        } else {
            ans.push_back(path[path.size() / 2]);
            ans.push_back(path[path.size() / 2 - 1]);
        }
        return ans;
    }
};