Make writing a habit together! This is the sixth day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.
Topic describes
This is the 310. Minimum height tree on LeetCode, medium difficulty.
Tag: “Tree DP”, “DFS”, “dynamic programming”
A tree is an undirected graph in which any two vertices are connected by only one path. In other words, any connected graph without a simple loop is a tree.
You are given a tree of NNN nodes labeled 000 to N − 1n-1n −1. Given the number NNN and a list of n− 1n-1N −1 undirected edges (each edge is a pair of labels), Where edges[I]=[ai, BI]edges[I]=[a_i, b_i]edges[I]=[ai,bi] indicates that there is an undirected edge between the nodes AIa_iai and BIB_ibi in the tree.
You can choose any node in the tree as the root. If node XXX is selected as the root node, set the height of the result tree to HHH. Of all possible trees, the tree with the minimum height (i.e., min(h)) is called a minimum height tree.
Find all the minimum height trees and return a list of their root node labels in any order.
The height of a tree is the number of points above the longest downward path between the root node and the leaf node.
Example 1:
Edges input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Explanation: As shown in the figure, when the root is a node labeled 1, the height of the tree is 1, which is the only minimum height tree.Copy the codeExample 2:
Input: n = 6, edges = [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]] output: [3, 4]Copy the codeTip:
- All (ai,bi)(ai, bi)(ai,bi) are different
- The given input is guaranteed to be a tree with no duplicate edges
The tree DP
This is a tree DP template problem.
When a certain point is determined as the root node, the shape of the whole tree is unique and fixed, so the node numbered 000 can be used as the root node for analysis.
Assume that the node currently processed is U, which is traversed from the parent node FA, and the child node to be traversed is J.
The tree looks like this (some possible outsides are indicated by dotted lines) :
Tree-shaped DP problems are usually divided into “directions”. For the node U currently processed, we divide it into “down” and “up” directions according to whether the “out-edge from FA to U” is considered.
Suppose that FFF array and GGG array are preprocessed by DFS, where F [u]f[u]f[u] represents the maximum descending height of the tree with point 000 as the root node and u node as the sub-root node. G [u]g[u]g[u] represents the maximum height of the tree with point 000 as the root node and u as the child node. So finally u as the maximum height of the root node as Max (f [u], g [u]) \ Max (f [u], g [u]) Max (f [u], g [u]).
Where F [u]f[u]f[u] can be processed only by simple DFS, but for g[u]g[u]g[u] g[u] also contains two parts of “up” and “down”. For part of Max up (g, g [fa] [u] + 1)/Max (g, g [fa] [u] + 1) Max (g, g [fa] [u] + 1), for part of the down, We need to consider whether the maximum value f[FA]f[FA]f[FA]f[FA] is involved by U node to carry out case-by-case discussion. If F [FA]f[FA]f[FA] itself is not involved by U, Then g[u]g[u]g[u] should be the maximum value of fa node down +1+1+1; If u node participates in the maximum value of fa downwards, g[u]g[u] should be updated with the sub-maximum value of FA downwards +1+1+1.
Therefore, we need to split the FFF array into recording “f1f1F1 array of maximum value” and recording “F2f2F2 array of sub-maximum value”, and use PPP array to record the value of j of u’s child node when obtaining F1 [u]f1[u]f1[u].
In addition, when dealing with DFS in the “upward” direction, we can change “update U with FA” to “update J with U” in order to avoid the processing of fa node being empty.
Code:
class Solution {
int N = 20010, M = N * 2, idx = 0;
int[] he = new int[N], e = new int[M], ne = new int[M];
int[] f1 = new int[N], f2 = new int[N], g = new int[N], p = new int[N];
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
Arrays.fill(he, -1);
for (int[] e : edges) {
int a = e[0], b = e[1];
add(a, b); add(b, a);
}
dfs1(0, -1);
dfs2(0, -1);
List<Integer> ans = new ArrayList<>();
int min = n;
for (int i = 0; i < n; i++) {
int cur = Math.max(f1[i], g[i]);
if (cur < min) {
min = cur;
ans.clear();
ans.add(i);
} else if(cur == min) { ans.add(i); }}return ans;
}
int dfs1(int u, int fa) {
for (inti = he[u]; i ! = -1; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
int sub = dfs1(j, u) + 1;
if (sub > f1[u]) {
f2[u] = f1[u];
f1[u] = sub;
p[u] = j;
} else if(sub > f2[u]) { f2[u] = sub; }}return f1[u];
}
void dfs2(int u, int fa) {
for (inti = he[u]; i ! = -1; i = ne[i]) {
int j = e[i];
if (j == fa) continue;
if(p[u] ! = j) g[j] = Math.max(g[j], f1[u] +1);
else g[j] = Math.max(g[j], f2[u] + 1);
g[j] = Math.max(g[j], g[u] + 1); dfs2(j, u); }}}Copy the code- Time complexity: O(n)O(n)O(n)
- Space complexity: O(n)O(n)O(n)
The last
This is the no.310 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks. We will first finish all the topics without locks.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.