当前位置：首页 > ds >正文

面试题：N叉数的最大深度

ds 2025/7/28 16:45:16

文章目录

面试题
力扣相同题目

面试题

题目描述：

旅行商来到了一个新的国家，这个国家有N个城市，他们直接由N-1条道路相连接，每条道路的长度不尽相同，旅行商现在在1号城市，若要每一个城市都游览一遍，需要行走的最短路程是多少

输入

第一行一个数N代表城市个数，(1<N<50000)
之后N-1行，每行三个数 x y z，代表x到y的距离为z

输出

输出最小距离

样例

输入
3
1 2 1
1 3 1
输出
3

思路
N个城市N-1条道路相连接，说明是一个无向无环图。从一个城市出发，每个城市都要走过一遍，说明一定要走回头路，即每条道路都要走两遍。但是实际上，最后一条路径上的道路只需走一遍即可，因为不需要回到起始点。假设道路长度总和为sum，最后一条路径道路总和为len
那么，旅行商需要行走的路程为2*sum-len，如果想要这个路程最短，就得让len最长。
至此，这道题目可以转化为求N叉数的最大深度
编程实现(go)

package mainimport "fmt"// 原题目描述：
/*
旅行商来到了一个新的国家，这个国家有N个城市，他们直接由N-1条道路相连接，
每条道路的长度不尽相同，旅行商现在在1号城市，若要每一个城市都游览一遍，需要行走的最短路程是多少
*/// 求N叉数的最大深度// 定义节点
type node struct {en  int //道路的终点val int //道路的长度
}// 定义一个邻接表存储N叉数
var ma [][]node
// 定义一个bool数组存储访问过的节点
var vis []bool// 定义一个函数用来给邻接表添加边
func add(st, en, val int) {nd := node{en:  en,val: val,}ma[st] = append(ma[st], nd)
}var maxdepth=0
// 计算最大深度，node表示起点城市
func getMaxDepth(node int,depth int){vis[node]=true if depth>maxdepth{maxdepth=depth}// 访问节点的邻边for _,nd:=range ma[node]{en,val:=nd.en,nd.valif !vis[en]{getMaxDepth(en,depth+val)}}
}func main() {// 输入一些数据var N int //城市个数fmt.Scanf("%d\n", &N)// 初始化邻接表，城市编号从1开始ma=make([][]node,N+1)// 初始化bool数组vis=make([]bool,N+1)var x,y,z int sum:=0// 输入的同时计算道路总和for range N-1{fmt.Scanf("%d %d %d\n",&x,&y,&z)sum+=z// 添加边add(x,y,z)add(y,x,z)}// 计算N叉数最大深度getMaxDepth(1,0)fmt.Printf("%d\n",2*sum-maxdepth)}

力扣相同题目

N叉数的最大深度

/*** Definition for a Node.* type Node struct {*     Val int*     Children []*Node* }*/func maxDepth(root *Node) int {var dfs func(*Node)int dfs=func(root *Node)int{if root==nil{return 0}maxdepth:=0for _,node:=range root.Children{depth:=dfs(node)if depth>maxdepth{maxdepth=depth}}return maxdepth+1}return dfs(root)
}