怎么做网站的关键词库,公司网站建设须知,电脑用虚拟机做网站,开发一个小软件多少钱2024.3.17 题目来源我的题解方法一 深度优先遍历方法二 广度优先遍历方法三 拓扑排序 题目来源
力扣每日一题#xff1b;题序#xff1a;310
我的题解
方法一 深度优先遍历 从每一个节点开始进行深度优先遍历并计算以该节点为根节点的树的深度#xff0c;使用哈希表存储对… 2024.3.17 题目来源我的题解方法一 深度优先遍历方法二 广度优先遍历方法三 拓扑排序 题目来源
力扣每日一题题序310
我的题解
方法一 深度优先遍历 从每一个节点开始进行深度优先遍历并计算以该节点为根节点的树的深度使用哈希表存储对应深度有哪些节点最后取出key最小对应的value的作为结果。超时。 时间复杂度O( n 2 n^2 n2) 空间复杂度O(n) TreeMapInteger,SetInteger mapnew TreeMap();
public ListInteger findMinHeightTrees(int n, int[][] edges) {ListInteger[] gcreateTree(n,edges);for(int i0;in;i){int minDeepdfs(g,i,i,-1,1);System.out.println(minDeep);SetInteger lmap.getOrDefault(minDeep,new HashSet());l.add(i);map.put(minDeep,l);}return new ArrayList(map.firstEntry().getValue());
}
public ListInteger[] createTree(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int from t[0];int to t[1];g[from].add(to);g[to].add(from);}return g;
}
public int dfs(ListInteger[] g,int root,int cur,int pre,int deepth){int minDeep0;for(int next:g[cur]){if(next!pre){int tdfs(g,root,next,cur,deepth1);minDeepMath.max(minDeep,t);}}return minDeep1;
}由于一定是树所以具有最小深度的根节点只有可能最多两个节点作为个根时的深度是相同的。所以可以求该图中最长的直径中间节点就是需要求的根节点。所以不用对所有节点都进行深度优先遍历只需要遍历两个节点就行了。 时间复杂度O(n) 空间复杂度O(n) //优化版本
TreeMapInteger,SetInteger mapnew TreeMap();
ListInteger pathnew ArrayList();
int deep0;
public ListInteger findMinHeightTrees(int n, int[][] edges) {ListInteger[] gcreateTree(n,edges);//优化的地方ListInteger pnew ArrayList();int x0;p.add(x);dfs(g,x,-1,1,p);pnew ArrayList();int ypath.get(path.size()-1);p.add(y);dfs(g,y,-1,1,p);int szpath.size();if(sz%20){return path.subList(sz/2-1,sz/21);}else{return path.subList(sz/2,sz/21);}
}
public ListInteger[] createTree(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int from t[0];int to t[1];g[from].add(to);g[to].add(from);}return g;
}
public void dfs(ListInteger[] g,int cur,int pre,int deepth,ListInteger p){if(deepthdeep){pathnew ArrayList(p);deepdeepth;}for(int next:g[cur]) {if (next ! pre) {p.add(next);dfs(g, next, cur, deepth 1, p);p.remove(p.size() - 1);}}
}方法二 广度优先遍历 在方法一的优化版本基础上也可以采用广度优先遍历来求最长直径。 时间复杂度O(n) 空间复杂度O(n) TreeMapInteger,SetInteger mapnew TreeMap();
ListInteger pathnew ArrayList();
int deep0;
public ListInteger findMinHeightTrees(int n, int[][] edges) {ListInteger[] gcreateTree(n,edges);//变化之处在于采用广度优先遍历求最长直径int x0;bfs(g,x);int ypath.get(path.size()-1);bfs(g,y);int szpath.size();if(sz%20){return path.subList(sz/2-1,sz/21);}else{return path.subList(sz/2,sz/21);}
}
public ListInteger[] createTree(int n,int[][] edges){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int from t[0];int to t[1];g[from].add(to);g[to].add(from);}return g;
}
public void bfs(ListInteger[] g,int cur){QueueInteger queuenew LinkedList();queue.offer(cur);int[] parentnew int[g.length];//记录路径parent[cur]-1;boolean[] visitednew boolean[g.length];visited[cur]true;//最后一层的节点int endcur;while(!queue.isEmpty()){int szqueue.size();for (int i 0; i sz; i) {int tqueue.poll();boolean ffalse;for(int next:g[t]){if(visited[next])continue;parent[next]t;visited[next]true;queue.offer(next);ftrue;}if(!f)endt;}}path.clear();while(end!-1){path.add(0,end);endparent[end];}
}方法三 拓扑排序 最小深度也可以看做是一直删除叶子节点最后剩下的一个或者两个节点就是满足条件的节点。这种每次删除叶子节点的操作实质就是拓扑排序。 时间复杂度O(n) 空间复杂度O(n) public ListInteger findMinHeightTrees(int n, int[][] edges) {//注意使用拓扑排序需要将只有一个节点的情况单独考虑if(n1)return Arrays.asList(0);int[] tpnew int[n];ListInteger[] gcreateTree(n,edges,tp);QueueInteger queuenew LinkedList();for(int i0;in;i){if(tp[i]1)queue.offer(i);}return tpFunc(g,tp,n,queue);
}
public ListInteger[] createTree(int n,int[][] edges,int[] tp){ListInteger[] gnew ArrayList[n];for(int i0;in;i){g[i]new ArrayList();}for(int[] t:edges){int from t[0];int to t[1];g[from].add(to);g[to].add(from);tp[from];tp[to];}return g;
}
public ListInteger tpFunc(ListInteger[] g,int[] tp,int remain,QueueInteger queue){ListInteger resnew ArrayList();while(remain2){int szqueue.size();remain-sz;for(int i0;isz;i){int tqueue.poll();for(int next:g[t]){tp[t]--;tp[next]--;if(tp[next]1)queue.offer(next);}}}while(!queue.isEmpty()){res.add(queue.poll());}return res;
}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
