• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode834.树中距离之和|SumofDistancesinTree

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址: https://www.cnblogs.com/strengthen/p/10576111.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

An undirected, connected tree with N nodes labelled 0...N-1 and N-1 edges are given.

The ith edge connects nodes edges[i][0]and edges[i][1] together.

Return a list ans, where ans[i] is the sum of the distances between node i and all other nodes.

Example 1:

Input: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
Output: [8,12,6,10,10,10]
Explanation: 
Here is a diagram of the given tree:
  0
 / \
1   2
   /|\
  3 4 5
We can see that dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5)
equals 1 + 1 + 2 + 2 + 2 = 8.  Hence, answer[0] = 8, and so on.

Note: 1 <= N <= 10000

 


 

给定一个无向、连通的树。树中有 N 个标记为 0...N-1 的节点以及 N-1 条边 。

 

第 i 条边连接节点 edges[i][0] 和 edges[i][1] 。

 

返回一个表示节点 i 与其他所有节点距离之和的列表 ans

 

示例 1:

 

输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 
如下为给定的树的示意图:
  0
 / \
1   2
   /|\
  3 4 5

我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此,answer[0] = 8,以此类推。

 

说明: 1 <= N <= 10000


Runtime: 364 ms
Memory Usage: 20.3 MB
 1 class Solution {
 2     var res:[Int] = [Int]()
 3     var count:[Int] = [Int]()
 4     var tree:[Set<Int>] = [Set<Int>]()
 5     func sumOfDistancesInTree(_ N: Int, _ edges: [[Int]]) -> [Int] {
 6         res = [Int](repeating:0,count:N)
 7         count = [Int](repeating:0,count:N)
 8         tree = [Set<Int>](repeating:Set<Int>(),count:N)
 9         for e in edges
10         {
11             tree[e[0]].insert(e[1])
12             tree[e[1]].insert(e[0])
13         }
14         dfs(0, -1)
15         dfs2(0, -1)
16         return res
17     }
18     
19     func dfs(_ root:Int,_ pre:Int)
20     {
21         for i in tree[root]
22         {
23             if i == pre {continue}
24             dfs(i, root)
25             count[root] += count[i]
26             res[root] += res[i] + count[i]
27         }
28         count[root] += 1        
29     }
30     
31     func dfs2(_ root:Int,_ pre:Int)
32     {
33         for i in tree[root]
34         {
35             if i == pre {continue}
36             res[i] = res[root] - count[i] + count.count - count[i]
37             dfs2(i, root)
38         }
39     }
40 }

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap