2026-11-04:树的加权和。用go语言,现有一棵含 n 个结点的有根树,结点编号从 0 到 n-1,根结点为 0。数组 parent 描述父子关系:parent[0] 为 -1,对于其余结点 i,parent[i] 是结点 i 的父结点编号。另有一个长度相同的数组 nums,其中 nums[i] 是结点 i 的数值。

规定根结点所在层数为 1,某个结点的深度等于从根到它经过的结点个数。整棵树的高度 h 等于所有结点深度的最大值。对于深度为 d 的结点 i,其权重按 nums[i] 乘以 (h - d + 1) 计算。要求计算所有结点权重相加后的总和。

1 <= n <= 100000。

n == parent.length == nums.length。

parent[0] == -1。

对于所有 i,其中 i 位于 [1, n - 1],均有 0 <= parent[i] <= n - 1。

1 <= nums[i] <= 1000000。

保证输入数组 parent 表示一棵以节点 0 为根节点的有效树。

在这里插入图片描述
打开网易新闻 查看精彩图片
在这里插入图片描述

输入: parent = [-1,0,0,0,2,2], nums = [5,2,3,1,4,6]。

输出: 37。

解释:

该树的高度为 3。

节点

nums[i]

深度(d)

权重

0

5

1

5 * (3 - 1 + 1) = 15

1

2

2

2 * (3 - 2 + 1) = 4

2

3

2

3 * (3 - 2 + 1) = 6

3

1

2

1 * (3 - 2 + 1) = 2

4

4

3

4 * (3 - 3 + 1) = 4

5

6

3

6 * (3 - 3 + 1) = 6

所有节点的权重之和为 15 + 4 + 6 + 2 + 4 + 6 = 37。

题目来自力扣4015。

大体步骤如下:

  1. 1.确定结点数量并准备树的存储结构

  • • 读取parent数组,其长度就是树的结点数n。

  • • 创建一个长度为n的邻接表,用来存放每个结点的所有子结点。

  • • 因为题目保证parent[0] = -1,且其余结点都只有一个父结点,所以从下标1开始遍历每个结点i:

    • • 找到它的父结点parent[i];

    • • 把结点i加入到父结点的子结点列表中。

  • • 完成后,就得到了从根结点0出发的完整有根树结构。

2.准备记录每个结点深度的数组

  • • 创建一个长度为n的depth数组。

  • • 根据代码中的定义,根结点0的深度记为0。

  • • 这里的“深度”表示从根结点到当前结点经过的边数,因此:

    • • 根结点深度为0;

    • • 根结点的直接子结点深度为1;

    • • 再往下一层深度为2,依此类推。

  • • 这个深度与题目中“根所在层数为 1”的定义相差 1,后面计算权重时会自然抵消。

3.通过深度优先搜索计算每个结点的深度,并求整棵树的高度

  • • 从根结点0开始进行深度优先搜索。

  • • 搜索函数的作用有两个:

    • • 在访问子结点时,设置子结点的深度为当前结点深度加 1;

    • • 返回以当前结点为根的子树高度,这里的“高度”按结点个数计算。

  • • 对于当前结点,初始记录一个局部最大高度为0。

  • • 遍历当前结点的每个子结点:

    • • 先令子结点的深度等于当前结点深度加 1;

    • • 再递归计算子结点所在子树的高度;

    • • 用子树的返回值更新当前结点的局部最大高度。

  • • 当前结点处理完所有子结点后,返回“局部最大高度 + 1”。

    • • 如果是叶子结点,没有子结点,局部最大高度为0,返回1,表示该叶子自身形成的高度为 1;

    • • 如果某个结点下面还有子树,则返回从该结点到最深叶子经过的结点个数。

  • • 从根结点调用搜索后,得到的返回值就是整棵树的高度h。

  • • 在示例中,整棵树的高度为3。

4.理解代码中深度与题目中层数的对应关系

  • • 代码中根结点深度depth[0] = 0。

  • • 题目中根结点层数d = 1。

  • • 对任意结点,有:

    • • 题目层数d = depth[i] + 1。

  • • 题目要求的权重是:

    • •nums[i] * (h - d + 1)。

  • • 将d = depth[i] + 1代入:

    • •h - d + 1 = h - (depth[i] + 1) + 1 = h - depth[i]。

  • • 所以代码中直接用nums[i] * (h - depth[i])计算权重,与题目公式完全一致。

5.遍历所有结点,累加加权和

  • • 准备好一个 64 位整数变量保存总和,避免结果溢出。

  • • 遍历每个结点i和它的数值nums[i]:

    • • 根据已经得到的整棵树高度h;

    • • 根据该结点的代码深度depth[i];

    • • 计算该结点的权重:nums[i] * (h - depth[i]);

    • • 将该权重累加到总和中。

  • • 示例中各结点情况为:

    • • 结点 0:深度 0,权重5 * (3 - 0) = 15;

    • • 结点 1:深度 1,权重2 * (3 - 1) = 4;

    • • 结点 2:深度 1,权重3 * (3 - 1) = 6;

    • • 结点 3:深度 1,权重1 * (3 - 1) = 2;

    • • 结点 4:深度 2,权重4 * (3 - 2) = 4;

    • • 结点 5:深度 2,权重6 * (3 - 2) = 6。

  • • 总和为:

    • •15 + 4 + 6 + 2 + 4 + 6 = 37。

6.返回并输出结果

  • • 遍历完成后,累加变量中保存的就是所有结点权重之和。

  • • 示例最终输出37。

时间复杂度分析:

  • • 建树需要遍历parent中除根结点外的所有结点,共O(n)。

  • • 深度优先搜索会访问每个结点一次,并处理每条父子边一次,共O(n)。

  • • 最后遍历nums累加权重,共O(n)。

  • • 因此总时间复杂度为O(n)。

额外空间复杂度分析:

  • • 邻接表需要存储所有子结点关系,空间为O(n)。

  • •depth数组长度为n,空间为O(n)。

  • • 深度优先搜索使用递归调用栈,最坏情况下树退化成链,递归深度为O(n);最好或平均情况下与树高有关。

  • • 因此总的最坏额外空间复杂度为O(n)。

Go完整代码如下:

package main

import (
"fmt"
)

func weightedSum(parent []int, nums []int) (ans int64) {
n := len(parent)
g := make([][]int, n)
for i := 1; i < n; i++ {
p := parent[i]
g[p] = append(g[p], i)
}

depth := make([]int, n)
var dfs func(int)int
dfs = func(x int) (h int) {
for _, y := range g[x] {
depth[y] = depth[x] + 1
h = max(h, dfs(y))
}
return h + 1
}
h := dfs(0)

for i, x := range nums {
ans += int64(x) * int64(h-depth[i])
}
return
}

func main() {
parent := []int{-1, 0, 0, 0, 2, 2}
nums := []int{5, 2, 3, 1, 4, 6}
result := weightedSum(parent, nums)
fmt.Println(result)
}
打开网易新闻 查看精彩图片

Python完整代码如下:

# -*-coding:utf-8-*-

def weighted_sum(parent, nums):
n = len(parent)
g = [[] for _ in range(n)]

for i in range(1, n):
p = parent[i]
g[p].append(i)

depth = [0] * n

def dfs(x):
h = 0
for y in g[x]:
depth[y] = depth[x] + 1
h = max(h, dfs(y))
return h + 1

h = dfs(0)

ans = 0
for i, x in enumerate(nums):
ans += x * (h - depth[i])

return ans

if __name__ == "__main__":
parent = [-1, 0, 0, 0, 2, 2]
nums = [5, 2, 3, 1, 4, 6]
result = weighted_sum(parent, nums)
print(result)
打开网易新闻 查看精彩图片

C++完整代码如下:

  





using namespace std;

long long weightedSum(const vector& parent, const vector& nums) {
int n = parent.size();
vector int >> g(n);

for ( int i = 1 ; i < n; ++i) {
int p = parent[i];
g[p].push_back(i);
}

vector< int > depth(n, 0 );

function< int ( int )> dfs = [&]( int x) -> int {
int h = 0 ;
for ( int y : g[x]) {
depth[y] = depth[x] + 1 ;
h = max(h, dfs(y));
}
return h + 1 ;
};

int h = dfs( 0 );

long long ans = 0 ;
for ( int i = 0 ; i < n; ++i) {
ans += 1 LL * nums[i] * (h - depth[i]);
}

return ans;
}

int main() {
vector< int > parent = { -1 , 0 , 0 , 0 , 2 , 2 };
vector< int > nums = { 5 , 2 , 3 , 1 , 4 , 6 };

long long result = weightedSum(parent, nums);
cout << result << endl;

return 0 ;
}
打开网易新闻 查看精彩图片

我们相信人工智能为普通人提供了一种“增强工具”,并致力于分享全方位的AI知识。在这里,您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”,发消息可获得面试资料,让AI助力您的未来发展。