What is the optimal time complexity for the Sum of Distances in Tree problem?

The optimal time complexity is O(n), where n is the number of nodes in the tree, achieved by using two passes of depth-first search.

How can dynamic programming help with this problem?

Dynamic programming helps by storing intermediate results, allowing for efficient propagation of distance sums without redundant calculations.

What’s the main challenge in solving the Sum of Distances in Tree problem?

The main challenge is efficiently computing the sum of distances for each node, which requires avoiding recalculating distances for every node pair.

Can breadth-first search (BFS) be used instead of depth-first search for this problem?

While BFS can be used, DFS is typically more efficient in this problem due to its natural recursive structure and ease of propagation for distance sums.

What should I focus on when approaching the Sum of Distances in Tree problem during an interview?

Focus on efficient tree traversal using DFS and dynamic programming to optimize the distance sum calculation for all nodes.

#834

Hard

auto_awesome图·DFS·traversal

LeetCode 题解工作台

树中距离之和

给定一个无向、连通的树。树中有 n 个标记为 0...n-1 的节点以及 n-1 条边。给定整数 n 和数组 edges ， edges[i] = [a i , b i ] 表示树中的节点 a i 和 b i 之间有一条边。返回长度为 n 的数组 answer ，其中 answer[i] 是树…

动态规划树深度优先搜索图

题目描述

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

给定整数 n 和数组 edges ， edges[i] = [a_i, b_i]表示树中的节点 a_i 和 b_i 之间有一条边。

返回长度为 n 的数组 answer ，其中 answer[i] 是树中第 i 个节点与所有其他节点之间的距离之和。

示例 1:

输入: n = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 树如图所示。
我们可以计算出 dist(0,1) + dist(0,2) + dist(0,3) + dist(0,4) + dist(0,5) 
也就是 1 + 1 + 2 + 2 + 2 = 8。 因此，answer[0] = 8，以此类推。

示例 2:

输入: n = 1, edges = []
输出: [0]

示例 3:

输入: n = 2, edges = [[1,0]]
输出: [1,1]

提示:

1 <= n <= 3 * 10⁴
edges.length == n - 1
edges[i].length == 2
0 <= a_i, b_i < n
a_i != b_i
给定的输入保证为有效的树

lightbulb

解题思路

方法一：树形 DP（换根）

我们先跑一遍 DFS，计算出每个节点的子树大小，记录在数组 $size$ 中，并且统计出节点 $0$ 到其他节点的距离之和，记录在 $ans[0]$ 中。

接下来，我们再跑一遍 DFS，枚举每个点作为根节点时，其他节点到根节点的距离之和。假设当前节点 $i$ 的答案为 $t$ ，当我们从节点 $i$ 转移到节点 $j$ 时，距离之和变为 $t - size[j] + n - size[j]$ ，即距离节点 $j$ 及其子树节点的距离之和减少 $size[j]$ ，而距离其它节点的距离之和增加 $n - size[j]$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为树的节点数。

相似题目：

2581. 统计可能的树根数目

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

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        def dfs1(i: int, fa: int, d: int):
            ans[0] += d
            size[i] = 1
            for j in g[i]:
                if j != fa:
                    dfs1(j, i, d + 1)
                    size[i] += size[j]

        def dfs2(i: int, fa: int, t: int):
            ans[i] = t
            for j in g[i]:
                if j != fa:
                    dfs2(j, i, t - size[j] + n - size[j])

        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)

        ans = [0] * n
        size = [0] * n
        dfs1(0, -1, 0)
        dfs2(0, -1, ans[0])
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate should demonstrate familiarity with tree traversal algorithms.
question_mark
The candidate must efficiently propagate calculations from one node to others.
question_mark
Look for a clear understanding of how dynamic programming can optimize the process.

warning

常见陷阱

外企场景

error
Misunderstanding the relationship between the sum of distances for a parent and its children, leading to inefficient recomputation.
error
Failing to use dynamic programming, resulting in redundant calculations and a time complexity that exceeds acceptable limits.
error
Not properly handling edge cases, such as when `n = 1` or `n = 2`.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to calculate the sum of distances for a specific subset of nodes rather than all nodes.
arrow_right_alt
Alter the tree structure by introducing different types of edges (e.g., weighted edges) and adjusting the solution approach.
arrow_right_alt
Explore the problem using a breadth-first search (BFS) approach instead of DFS to see how the complexity and approach might change.

help

常见问题

外企场景

继续练习

#787 K 站中转内最便宜的航班 #968 监控二叉树 #337 打家劫舍 III