05.04.06-Exercises.md

05.02.06 练习题目（第 12 天）

1. 0687. 最长同值路径

1.1 题目大意

描述：给定一个二叉树的根节点 $root$。

要求：返回二叉树中最长的路径的长度，该路径中每个节点具有相同值。 这条路径可以经过也可以不经过根节点。

说明：

• 树的节点数的范围是 $[0, 10^4]$。
• $-1000 \le Node.val \le 1000$。
• 树的深度将不超过 $1000$。
• 两个节点之间的路径长度：由它们之间的边数表示。

示例：

• 示例 1：

输入：root = [5,4,5,1,1,5]
输出：2

• 示例 2：

输入：root = [1,4,5,4,4,5]
输出：2

2. 1617. 统计子树中城市之间最大距离

2.1 题目大意

描述：给定一个整数 $n$，代表 $n$ 个城市，城市编号为 $1 \sim n$。同时给定一个大小为 $n - 1$ 的数组 $edges$，其中 $edges[i] = [u_i, v_i]$ 表示城市 $u_i$ 和 $v_i$ 之间有一条双向边。题目保证任意城市之间只有唯一的一条路径。换句话说，所有城市形成了一棵树。

要求：返回一个大小为 $n - 1$ 的数组，其中第 $i$ 个元素（下标从 $1$ 开始）是城市间距离恰好等于 $i$ 的子树数目。

说明：

• 两个城市间距离：定义为它们之间需要经过的边的数目。
• 一棵子树：城市的一个子集，且子集中任意城市之间可以通过子集中的其他城市和边到达。两个子树被认为不一样的条件是至少有一个城市在其中一棵子树中存在，但在另一棵子树中不存在。
• $2 \le n \le 15$。
• $edges.length == n - 1$。
• $edges[i].length == 2$。
• $1 \le u_i, v_i \le n$。
• 题目保证 $(ui, vi)$ 所表示的边互不相同。

示例：

• 示例 1：

输入：n = 4, edges = [[1,2],[2,3],[2,4]]
输出：[3,4,0]
解释：
子树 {1,2}, {2,3} 和 {2,4} 最大距离都是 1 。
子树 {1,2,3}, {1,2,4}, {2,3,4} 和 {1,2,3,4} 最大距离都为 2 。
不存在城市间最大距离为 3 的子树。

• 示例 2：

输入：n = 2, edges = [[1,2]]
输出：[1]

3. 0834. 树中距离之和

3.1 题目大意

描述：给定一个无向、连通的树。树中有 $n$ 个标记为 $0 \sim n - 1$ 的节点以及 $n - 1$ 条边 。

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

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

说明：

• $1 \le n \le 3 \times 10^4$。
• $edges.length == n - 1$。
• $edges[i].length == 2$。
• $0 \le ai, bi < n$。
• $ai \ne bi$。
• 给定的输入保证为有效的树。

示例：

• 示例 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 = 2, edges = [[1,0]]
输出: [1,1]

习题解析

1. 「0687. 最长同值路径」习题解析：网页链接、Github 链接
2. 「1617. 统计子树中城市之间最大距离」习题解析：网页链接、Github 链接
3. 「0834. 树中距离之和」习题解析：网页链接、Github 链接