8.26华为OD机试真题 新系统 – 部门绩效汇总 (JavaPyCC++JsGo)
2026 华为OD机试真题8月26日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
某公司使用二叉树结构管理组织汇报关系：每个节点代表一名员工，员工的“左下属”为研发组成员，“右下属”为产品组成员。若某侧无下属，则对应位置为空。
年终绩效考核时，每位员工有一个基础绩效分。按照公司制度，管理者的最终绩效分 = 自身基础分 + 左子树所有员工的最终绩效分之和 + 右子树所有员工的最终绩效分之和。
请根据给定公司完整的员工树结构以及每位员工的基础绩效分，计算并返回每位员工的最终绩效分。
2026 华为OD机试真题8月26日华为OD上机新系统考试真题 100 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
输入描述
共有 4 个输入参数：
n：员工总数（1 ≤ n ≤ 1000），编号到n-1。left：长度为n的整数数组，left[i]表示其左下属的编号，-1表示无。right：长度为n的整数数组，right[i]表示其右下属的编号，-1表示无。base：长度为n的整数数组，base[i]表示该员工的基础绩效分，0 ≤ base[i] ≤ 10000。
约束：
- 员工编号无重复、无遗漏。
- 整棵树为一棵合法的二叉树，有且仅有一个根节点。
输出描述
长度为 n 的数组，第 i 个元素表示员工 i 的最终绩效分。顺序与员工编号顺序一致。
示例1
输入
1,[-1],[-1],[10]输出
[10]说明
公司只有一名员工 0，无下属，最终绩效分等于其基础绩效分 10。
示例2
输入
5,[1,3,-1,-1,-1],[2,-1,4,-1,-1],[5,3,2,4,7]输出
[21,7,9,4,7]说明
树结构如下（括号内为基础绩效分）：
0(5) / \ 1(3) 2(2) / \ 3(4) 4(7)计算过程（后序遍历）：
- 员工 3：4
- 员工 4：7
- 员工 1：3+4=7
- 员工 2：2+7=9
- 员工 0：5+7+9=21
按编号顺序返回最终绩效分：
[21,7,9,4,7]。
解题思路
核心思想
每个员工的最终绩效分都依赖于左右子树的最终绩效分，因此这是一个标准的后序汇总问题。先找到树根，再按“孩子先算完、父节点最后算”的顺序累加即可。
算法步骤
- 遍历
left和right，标记所有出现过的子节点。 - 没有被标记为子节点的那个节点就是根。
- 用栈做一次前序遍历，记录节点访问顺序。
- 将访问顺序反转，得到后序顺序。
- 按后序顺序更新每个节点：
ans[u] = base[u] + ans[left[u]] + ans[right[u]]。 - 返回按编号顺序的最终绩效数组。
复杂度分析
设员工总数为 n。
- 找根节点：
O(n) - 遍历并反向得到后序顺序：
O(n) - 统一累加子树贡献：
O(n) - 总时间复杂度：
O(n) - 额外空间复杂度：`O
版权声明：
作者：魔改工程师
链接：https://www.sylblog.xin/archives/862
文章版权归作者所有，未经允许请勿转载。
THE END
