# DP in C++

• I implement the dynamic programming idea described in another post. Although the implementation in lengthy, that is an interesting idea for me.

``````    v
/  |  \
0   u   0
/ | \
0  0  0
(0 denotes a subtree)
``````

The key observation is the recursive formula:
height of tree at u = max(longest path of graph ending at u but not in the subtree of u, longest path in subtree of u)
where
the longest path of graph ending at u but not in the subtree of u = longest or second longest path at parent v + 1 (one edge v->u)

Time: O(n) because each node is visited 2 times, space : O(n) for the arrays

``````class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
if (n == 1)
return vector<int> (1, 0);
vector<vector<int>> graph(n);
for (pair<int, int> edge : edges) {
graph[edge.first].emplace_back(edge.second);
graph[edge.second].emplace_back(edge.first);
}

vector<int> longest(n), s_longest(n);
findLongestPathsFrom(0, -1, longest, s_longest, graph);

vector<int> heights(n);
findHeightsFrom(0, -1, 1, heights, longest, s_longest, graph);

vector<int> result;
int min_h = n;
for (int i = 0; i < n; ++i) {
if (min_h >= heights[i]) {
if (heights[i] < min_h) {
min_h = heights[i];
result.clear();
}
result.emplace_back(i);
}
}
return result;
}

void findLongestPathsFrom(int root, int parent, vector<int>& longest, vector<int>& s_longest, const vector<vector<int>>& graph) {
longest[root] = 1;
s_longest[root] = 1;

for (int child : graph[root]) {
if (child == parent)
continue;
findLongestPathsFrom(child, root, longest, s_longest, graph);

int tmp = longest[child] + 1;
if (tmp > longest[root]) {
s_longest[root] = longest[root];
longest[root] = longest[child] + 1;
} else if (tmp > s_longest[root]) {
s_longest[root] = longest[child] + 1;
}
}
}

void findHeightsFrom(int root, int parent, int upper_longest, vector<int>& heights, const vector<int>& longest, const vector<int>& s_longest, const vector<vector<int>>& graph) {
heights[root] = max(upper_longest, longest[root]);
for (int child : graph[root]) {
if (child == parent)
continue;

int child_upper_longest = max(upper_longest, longest[child] + 1 == longest[root] ? s_longest[root]: longest[root]);

findHeightsFrom(child, root, child_upper_longest + 1, heights, longest, s_longest, graph);
}
}

};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.