- Difficulty: Medium.

- Related Topics: Depth-First Search, Breadth-First Search, Graph, Topological Sort.

- Similar Questions: Course Schedule, Course Schedule II, Collect Coins in a Tree, Count Pairs of Connectable Servers in a Weighted Tree Network.

A tree is an undirected graph in which any two vertices are connected by *exactly* one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of`n` nodes labelled from`0` to`n - 1`, and an array of `n - 1` `edges` where`edges[i] = [ai, bi]` indicates that there is an undirected edge between the two nodes `ai` and `bi` in the tree, you can choose any node of the tree as the root. When you select a node`x` as the root, the result tree has height`h`. Among all possible rooted trees, those with minimum height (i.e.`min(h)`)  are called**minimum height trees** (MHTs).

Return**a list of all**MHTs'** root labels**. You can return the answer in**any order**.

The**height** of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

 

Example 1:

Example 2:

 

**Constraints:**

- All the pairs`(ai, bi)` are distinct.

- The given input is**guaranteed** to be a tree and there will be**no repeated** edges.

varfindMinHeightTrees=function(n,edges) {

if (!edges.length)return [0];

var map=Array(n).fill(0).map(()=>newMap());

for (var i=0; i<edges.length; i++) {

map[edges[i][0]].set(edges[i][1],true);

map[edges[i][1]].set(edges[i][0],true);

}

var arr= [];

for (var i=0; i< n; i++) {

if (map[i].size===1) {

arr.push(i);

}

}

while (n>2) {

n-=arr.length;

var newArr= [];

for (var i=0; i<arr.length; i++) {

var j=Array.from(map[arr[i]].keys())[0];

map[j].delete(arr[i]);

if (map[j].size===1) {

newArr.push(j);

}

}

arr= newArr;

}

return arr;

};

**Explain:**

Delete every leaf untill there is only one or two nodes.

**Complexity:**

* Time complexity : O(n).

* Space complexity : O(n).

- Difficulty: Medium.

- Related Topics: Array, Hash Table, String, Breadth-First Search.

- Similar Questions: Reachable Nodes With Restrictions.

You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:`'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'`. The wheels can rotate freely and wrap around: for example we can turn`'9'` to be`'0'`, or`'0'` to be`'9'`. Each move consists of turning one wheel one slot.

The lock initially starts at`'0000'`, a string representing the state of the 4 wheels.

You are given a list of`deadends` dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.

Given a`target` representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.

 

Example 1:

Example 2:

Example 3:

 

**Constraints:**

- target**will not be** in the list`deadends`.

-`target` and`deadends[i]` consist of digits only.

varopenLock=function(deadends,target) {

if (target==='0000')return0;

var arr= ['0000'];

var visited= {'0000':true };

var deadendsMap= {};

for (var i=0; i<deadends.length; i++) {

if (deadends[i]==='0000')return-1;

deadendsMap[deadends[i]]=true;

}

var res=0;

while (arr.length) {

var newArr= [];

res+=1;

for (var i=0; i<arr.length; i++) {

var nexts=getNexts(arr[i]);

for (var j=0; j<nexts.length; j++) {

if (nexts[j]=== target)return res;

if (!visited[nexts[j]]&&!deadendsMap[nexts[j]]) {

newArr.push(nexts[j]);

visited[nexts[j]]=true;

}

}

}

arr= newArr;

}

return-1;

};

vargetNexts=function(str) {

var res= [];

for (var i=0; i<str.length; i++) {

var num=Number(str[i]);

res.push(str.slice(0, i)+ (num===9?0: num+1)+str.slice(i+1));

res.push(str.slice(0, i)+ (num===0?9: num-1)+str.slice(i+1));

}

return res;

};

**Explain:**

nope.

**Complexity:**

* Time complexity : O(n).

* Space complexity : O(n).