给定一棵多叉树，求出这棵树的直径，即树上最远两点的距离。 包含n个结点，n-1条边的连通图称为树。 示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11 数据范围：，保证最终结果满足 要求：空间复杂度：，时间复杂度
示例1
输入
6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
输出
11
示例2
输入
2,[[0,1],[1,2]],[1]
输出
1
加载中...
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) { // write code here } }
/** * struct Interval { * int start; * int end; * Interval(int s, int e) : start(start), end(e) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类vector 树的边 * @param Edge_value int整型vector 边的权值 * @return int整型 */ int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) { // write code here } };
#coding:utf-8 # class Interval: # def __init__(self, a=0, b=0): # self.start = a # self.end = b # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 树的直径 # @param n int整型 树的节点个数 # @param Tree_edge Interval类一维数组 树的边 # @param Edge_value int整型一维数组 边的权值 # @return int整型 # class Solution: def solve(self , n , Tree_edge , Edge_value ): # write code here
using System; using System.Collections.Generic; /* public class Interval { public int start; public int end; public Interval () { start = 0; end = 0; } public Interval (int s, int e) { start = s; end = e; } } */ class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ public int solve (int n, List<Interval> Tree_edge, List<int> Edge_value) { // write code here } }
/* * function Interval(a, b){ * this.start = a || 0; * this.end = b || 0; * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ function solve( n , Tree_edge , Edge_value ) { // write code here } module.exports = { solve : solve };
<?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 ) { // write code here }
# class Interval: # def __init__(self, a=0, b=0): # self.start = a # self.end = b # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 树的直径 # @param n int整型 树的节点个数 # @param Tree_edge Interval类一维数组 树的边 # @param Edge_value int整型一维数组 边的权值 # @return int整型 # class Solution: def solve(self , n: int, Tree_edge: List[Interval], Edge_value: List[int]) -> int: # write code here
package main import "fmt" 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 { // write code here }
/** * struct Interval { * int start; * int end; * }; */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Tree_edgeLen int Tree_edge数组长度 * @param Edge_value int整型一维数组 边的权值 * @param Edge_valueLen int Edge_value数组长度 * @return int整型 */ int solve(int n, struct Interval* Tree_edge, int Tree_edgeLen, int* Edge_value, int Edge_valueLen ) { // write code here }
# class Interval # attr_accessor :start, :end # # def initialize(a = 0, b = 0) # @start, @end = a, b # end # end # # # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 树的直径 # @param n int整型 树的节点个数 # @param Tree_edge Interval类一维数组 树的边 # @param Edge_value int整型一维数组 边的权值 # @return int整型 # class Solution def solve(n, Tree_edge, Edge_value) # write code here end end
/** * class Interval(var start: Int, var end: Int) */ object Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ def solve(n: Int,Tree_edge: Array[Interval],Edge_value: Array[Int]): Int = { // write code here } }
/** * class Interval(var start: Int, var end: Int) */ object Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ fun solve(n: Int,Tree_edge: Array<Interval?>,Edge_value: IntArray): Int { // write code here } }
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) { // write code here } }
/*class Interval { * start: number * end: number * constructor(start: number, end: number) { * this.start = start * this.end = end * } * } */ /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ export function solve(n: number, Tree_edge: Interval[], Edge_value: number[]): number { // write code here }
/** * public class Interval { * public var start: Int * public var end: Int * public init(_ start: Int = 0, _ end: Int = 0) { * self.start = start * self.end = end * } * } */ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ func solve ( _ n: Int, _ Tree_edge: [Interval], _ Edge_value: [Int]) -> Int { // write code here } }
/** * #[derive(PartialEq, Eq, Clone, Debug)] * pub struct Interval { * pub start: i32, * pub end: i32, * } * * impl Interval { * #[inline] * fn new(start: i32, end: i32) -> Self { * Interval { * start: start, * end: end, * } * } * } */ struct Solution{ } impl Solution { fn new() -> Self { Solution{} } /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 树的直径 * @param n int整型 树的节点个数 * @param Tree_edge Interval类一维数组 树的边 * @param Edge_value int整型一维数组 边的权值 * @return int整型 */ pub fn solve(&self, n: i32, Tree_edge: Vec<Interval>, Edge_value: Vec<i32>) -> i32 { // write code here } }
6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
11
2,[[0,1],[1,2]],[1]
1