摘要:可以從頭邊同時進行,查看葉子節點并加入到葉子節點鏈表遍歷一遍后,葉子節點鏈表為。將葉子節點保存下來。這個時候就會有第二層葉子節點那些在列表當中為的點,用同樣的方法進行剝除。最后留在葉子節點里面的點即可以為根。
題目:
For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.
Format The graph contains n nodes which are labeled from 0 to n - 1.
You will be given the number n and a list of undirected edges (each
edge is a pair of labels).You can assume that no duplicate edges will appear in edges. Since all
edges are undirected, [0, 1] is the same as [1, 0] and thus will not
appear together in edges.
解法:
因為樹就是兩個點被一條線鏈接的無向圖,所以先用一個list把樹存成無向圖的列表。可以從頭邊同時進行,查看葉子節點并加入到葉子節點鏈表(遍歷一遍后,葉子節點鏈表size 為1)。 將葉子節點保存下來。這些葉子節點不用再查,但是剩余的中間節點,要依次查看,把跟第一層葉子節點有關的圖的矩陣里對應的記錄全部刪除,類似于剝除最外面一圈所有的點。 這個時候就會有第二層葉子節點(那些在列表當中size為1的點),用同樣的方法進行剝除。最后留在葉子節點list里面的點即可以為根。
代碼:
public ListfindMinHeightTrees(int n, int[][] edges) { List leaves = new ArrayList<>(); if (n == 1) { leaves.add(0); return leaves; } List > adj = new ArrayList<>(); for(int i = 0; i < n; i++) adj.add(new HashSet<>()); for(int[] edge : edges){ adj.get(edge[0]).add(edge[1]); adj.get(edge[1]).add(edge[0]); } for(int i = 0; i < n; i++) if(adj.get(i).size()==1) leaves.add(i); while(n > 2){ n-=leaves.size(); List newLeaves = new ArrayList<>(); for(int i : leaves){ for(int j : adj.get(i)){ adj.get(j).remove(i); if(adj.get(j).size() ==1) newLeaves.add(j); } } leaves = newLeaves; } return leaves; }
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66472.html
摘要:現在要求在這樣一棵生成樹中,找到生成樹的高度最低的所有根節點。然后利用鄰接表的相關屬性來判斷當前節點是否是葉節點。度數為一的頂點就是葉節點。這里使用異或的原因是對同一個值進行兩次異或即可以回到最初值。 題目 For an undirected graph with tree characteristics, we can choose any node as the root. The...
摘要:題目鏈接圖的題,和差不多。來解,每次放入只有一個的現在的。然后直到只剩最上面一層。注意考慮單獨的和別的不相連。比如這種情況,就有三個點都不和別的相連。還有的時候就要返回。 Minimum Height Trees 題目鏈接:https://leetcode.com/problems... 圖的題,和course schedule差不多。bfs來解,每次放入只有一個edge的node(現...
Problem You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map: 0 represents the obstacle cant be reached.1 represents the ground ...
Problem Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required. Example 1: Input: [[0, 30],[5,...
Unique Binary Search Trees Problem Given n, how many structurally unique BSTs (binary search trees) that store values 1...n? Example Given n = 3, there are a total of 5 unique BSTs. 1 3 3...
閱讀 1273·2023-04-25 23:22
閱讀 1673·2023-04-25 20:04
閱讀 2648·2021-11-22 15:24
閱讀 2806·2021-11-11 16:54
閱讀 1887·2019-08-30 14:03
閱讀 1484·2019-08-29 16:35
閱讀 1706·2019-08-26 10:29
閱讀 2661·2019-08-23 18:01