Commit3e1c0b7

committed

minimum_height_trees

1 parent71b7dd8 commit3e1c0b7Copy full SHA for 3e1c0b7

File tree

+28

-0

lines changed

+28

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -226,6 +226,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t`
`226`	`226`	`####[306. Additive Number](https://github.com/hitzzc/go-leetcode/tree/master/additive_number)`
`227`	`227`	`####[307. Range Sum Query - Mutable](https://github.com/hitzzc/go-leetcode/tree/master/range_sum_query_mutable)`
`228`	`228`	`####[309. Best Time to Buy and Sell Stock with Cooldown](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock_with_cooldown)`
	`229`	`+####[310. Minimum Height Trees](https://github.com/hitzzc/go-leetcode/tree/master/minimum_height_trees)`
`229`	`230`
`230`	`231`
`231`	`232`

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+classSolution {`
	`2`	`+public:`
	`3`	`+ vector<int>findMinHeightTrees(int n, vector<pair<int,int>>& edges) {`
	`4`	`+if (n <=1)return {0};`
	`5`	`+ vector<unordered_set<int>>graph(n);`
	`6`	`+for (auto& edge: edges) {`
	`7`	`+ graph[edge.first].insert(edge.second);`
	`8`	`+ graph[edge.second].insert(edge.first);`
	`9`	`+ }`
	`10`	`+ vector<int> current;`
	`11`	`+for (int i =0; i < graph.size(); ++i) {`
	`12`	`+if (graph[i].size() ==1) current.push_back(i);`
	`13`	`+ }`
	`14`	`+while (true) {`
	`15`	`+ vector<int> next;`
	`16`	`+for (auto& node: current) {`
	`17`	`+for (auto& neighbor: graph[node]) {`
	`18`	`+ graph[neighbor].erase(node);`
	`19`	`+if (graph[neighbor].size() ==1) next.push_back(neighbor);`
	`20`	`+ }`
	`21`	`+ }`
	`22`	`+if (next.size() ==0)break;`
	`23`	`+ current.swap(next);`
	`24`	`+ }`
	`25`	`+return current;`
	`26`	`+ }`
	`27`	`+};`

Comments

(0)