1443. Minimum Time to Collect All Apples in a Tree¶
题目信息¶
- 题号:
1443
- 难度:
Medium
- 主题:
树、深度优先搜索、子树统计
- 原题:
- 重点:
从节点
0出发,经过一条边耗时一秒,收集全部苹果后必须返回节点0;只需往返包含苹果的分支
题目重述¶
给定一棵包含 n 个节点的无向树,节点编号为 0 到 n-1,edges 给出边,hasApple[i] 表示节点 i 是否有苹果。
从节点 0 出发,沿边移动,每条边耗时一秒。收集所有苹果后必须回到节点 0。请返回完成任务所需的最少时间。
1 <= n <= 10^5,edges.length == n - 1,输入保证构成一棵树。
自建示例¶
最深苹果所在路径上的边都需往返:
输入:n = 3, edges = [[0,1],[1,2]], hasApple = [false,false,true]
输出:4
解释:需要经过两条边到达节点 2,再沿原路返回,共四秒。
没有任何苹果时无需移动:
输入:n = 2, edges = [[0,1]], hasApple = [false,false]
输出:0
解释:起点已经满足收集全部苹果的要求。