牛客NC99 多叉树的直径【较难 深度优先 Java/Go/PHP】

题目

题目链接：
https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3

思路

核心就是树的最大直径(globalMax)一定是以某一个node为root最长的两个path-to-leaf.
就是普通dfs的同时算路径长度。

时间: O(n), DFS一次
空间: O(n)
1
2
3
4
5

参考答案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}, ... }
        Map<Integer, List<int[]>> graph = new HashMap<>();
        int[] globalMax = {0};
        // construct graph
        for (int i = 0; i < n ; i++) {
            graph.put(i, new ArrayList<int[]>());
        }

        for (int i = 0; i < n - 1 ; i++) {
            // treat tree edge as bi-directional
            int 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 作为parent
        dfs(graph, globalMax, 0, -1);
        return globalMax[0];
    }
    // returns the max cost path-to-leaf from this root.
    public int dfs(Map<Integer, List<int[]>> 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 leaf
            int cost = dfs(graph, ans, nexts[0], root) + nexts[1];
            // keep 2 largest cost
            if (cost >= maxCost) {
                maxCost2 = maxCost;
                maxCost = cost;
            } else if(cost >=maxCost2){
                maxCost2 = cost;
            }
        }

        // check if the 2 largest path is the global max
        int curcost = maxCost + maxCost2;
        if (curcost > ans[0]) {
            ans[0] = curcost;
        }

        return maxCost;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

参考答案Go

package main

import . "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 graph
	for i := 0; i < n; i++ {
		graph[i] = []*Node{}
	}
	for i := 0; i < n-1; i++ {
		// treat tree edge as bi-directional
		from := Tree_edge[i].Start
		to := Tree_edge[i].End

		graph[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 作为parent
	ans := []int{0}
	dfs(graph, &ans, 0, -1)
	return ans[0]
}

func dfs(graph map[int][]*Node, ans *[]int, root, parent int) int {
	maxCost := 0
	maxCost2 := 0
	for _, 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 leaf
		cost := dfs(graph, ans, nexts.to, root) + nexts.cost
		// keep 2 largest cost
		if cost >= maxCost {
			maxCost2 = maxCost
			maxCost = cost
		} else if cost >= maxCost2 {
			maxCost2 = cost
		}

	}
	// check if the 2 largest path is the global max
	cursot := maxCost + maxCost2
	if cursot > (*ans)[0] {
		(*ans)[0] = cursot
	}

	return maxCost
}

type Node struct {
	to   int
	cost int
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81

参考答案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($i=0;$i<$n;$i++){
        $graph[$i] = [];
    }
    // construct graph
    for($i=0;$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 作为parent
    dfs($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 cost
        if($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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77