南阳网站推广,网站代理合作,公司名称变更网站要重新备案吗,北京通州做网站题目 题目链接#xff1a; https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3
思路
核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.
就是普通dfs的同时算路径长度。时间: O(n), DFS一次
空间: O(n)参考答案Java
impo…题目 题目链接 https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3
思路
核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.
就是普通dfs的同时算路径长度。时间: O(n), DFS一次
空间: O(n)参考答案Java
import java.util.*;/** public class Interval {* int start;* int end;* public Interval(int start, int end) {* this.start start;* this.end end;* }* }*/public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 树的直径* param n int整型 树的节点个数* param Tree_edge Interval类一维数组 树的边* param Edge_value int整型一维数组 边的权值* return int整型*/public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {//核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.//就是普通dfs的同时算路径长度。////时间: O(n), DFS一次//空间: O(n)// node_id - { {nei1, cost1}, {nei2, cost2}, ... }MapInteger, Listint[] graph new HashMap();int[] globalMax {0};// construct graphfor (int i 0; i n ; i) {graph.put(i, new ArrayListint[]());}for (int i 0; i n - 1 ; i) {// treat tree edge as bi-directionalint from Tree_edge[i].start;int to Tree_edge[i].end;graph.get(from).add(new int[] {to, Edge_value[i]});graph.get(to).add(new int[] {from, Edge_value[i]});}// 因为edge是bi-directional, 随便从哪个node开始dfs都一样。这里用了node-0.// -1 作为parentdfs(graph, globalMax, 0, -1);return globalMax[0];}// returns the max cost path-to-leaf from this root.public int dfs(MapInteger, Listint[] graph, int[] ans, int root,int parent) {int maxCost 0;int maxCost2 0;for (int[] nexts : graph.get(root)) {// NOTE: BaseCase (i.e. leaf) has only 1 nei, which is the parent// thus leaf will return maxCost 0 directly.if (nexts[0] parent) continue;// recursively finds the max cost path to any leafint cost dfs(graph, ans, nexts[0], root) nexts[1];// keep 2 largest costif (cost maxCost) {maxCost2 maxCost;maxCost cost;} else if(cost maxCost2){maxCost2 cost;}}// check if the 2 largest path is the global maxint curcost maxCost maxCost2;if (curcost ans[0]) {ans[0] curcost;}return maxCost;}
}参考答案Go
package mainimport . nc_tools/** type Interval struct {* Start int* End int* }*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 树的直径* param n int整型 树的节点个数* param Tree_edge Interval类一维数组 树的边* param Edge_value int整型一维数组 边的权值* return int整型*/
func solve(n int, Tree_edge []*Interval, Edge_value []int) int {//核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.//就是普通dfs的同时算路径长度。////时间: O(n), DFS一次//空间: O(n)// node_id - { {nei1, cost1}, {nei2, cost2}, ... }graph : map[int][]*Node{} //map表示图// construct graphfor i : 0; i n; i {graph[i] []*Node{}}for i : 0; i n-1; i {// treat tree edge as bi-directionalfrom : Tree_edge[i].Startto : Tree_edge[i].Endgraph[from] append(graph[from], Node{to, Edge_value[i]})graph[to] append(graph[to], Node{from, Edge_value[i]})}// 因为edge是bi-directional, 随便从哪个node开始dfs都一样。这里用了node-0.// -1 作为parentans : []int{0}dfs(graph, ans, 0, -1)return ans[0]
}func dfs(graph map[int][]*Node, ans *[]int, root, parent int) int {maxCost : 0maxCost2 : 0for _, nexts : range graph[root] {// NOTE: BaseCase (i.e. leaf) has only 1 nei, which is the parent// thus leaf will return maxCost 0 directly.if nexts.to parent {continue}// recursively finds the max cost path to any leafcost : dfs(graph, ans, nexts.to, root) nexts.cost// keep 2 largest costif cost maxCost {maxCost2 maxCostmaxCost cost} else if cost maxCost2 {maxCost2 cost}}// check if the 2 largest path is the global maxcursot : maxCost maxCost2if cursot (*ans)[0] {(*ans)[0] cursot}return maxCost
}type Node struct {to intcost int
}
参考答案PHP
?php/*class Interval{var $start 0;var $end 0;function __construct($a, $b){$this-start $a;$this-end $b;}
}*//*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 树的直径* param n int整型 树的节点个数* param Tree_edge Interval类一维数组 树的边* param Edge_value int整型一维数组 边的权值* return int整型*/
function solve( $n , $Tree_edge , $Edge_value )
{//核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.//就是普通dfs的同时算路径长度。////时间: O(n), DFS一次//空间: O(n)// node_id - { {nei1, cost1}, {nei2, cost2}, ... }$graph [];for($i0;$i$n;$i){$graph[$i] [];}// construct graphfor($i0;$i$n-1;$i){$from $Tree_edge[$i]-start;$to $Tree_edge[$i]-end;$graph[$from][count($graph[$from])] [$to,$Edge_value[$i]];$graph[$to][count($graph[$to])] [$from,$Edge_value[$i]];}$ans [0];// 因为edge是bi-directional, 随便从哪个node开始dfs都一样。这里用了node-0.// -1 作为parentdfs($graph,$ans,0,-1);return $ans[0];
}// returns the max cost path-to-leaf from this root.
function dfs($graph,$ans,$root,$parent){$max1 0;$max2 0;foreach ($graph[$root] as $nexts) {// NOTE: BaseCase (i.e. leaf) has only 1 nei, which is the parent// thus leaf will return maxCost 0 directly.if($nexts[0] $parent) continue; //不走回头路// recursively finds the max cost path to any leaf$cost dfs($graph,$ans,$nexts[0],$root)$nexts[1];// keep 2 largest costif($cost $max1){$max2$max1;$max1 $cost;}else if($cost $max2){$max2 $cost;}}// check if the 2 largest path is the global max$curcost $max1$max2;if($curcost $ans[0]){$ans[0] $curcost;}return $max1;
}
