6. 部门绩效汇总[200分]

题目内容

某公司使用二叉树结构管理组织汇报关系：每个节点代表一名员工，员工的“左下属”为研发组成员，“右下属”为产品组成员。若某侧无下属，则对应位置为空。

年终绩效考核时，每位员工有一个基础绩效分。按照公司制度，管理者的最终绩效分 = 自身基础分 + 左子树所有员工的最终绩效分之和 + 右子树所有员工的最终绩效分之和。

请根据给定公司完整的员工树结构以及每位员工的基础绩效分，计算并返回每位员工的最终绩效分。

输入描述

共有 4 个输入参数：

• n：员工总数（1 ≤ n ≤ 1000），编号 0 到 n-1。
• left：长度为 n 的整数数组，left[i] 表示其左下属的编号，-1 表示无。
• right：长度为 n 的整数数组，right[i] 表示其右下属的编号，-1 表示无。
• base：长度为 n 的整数数组，base[i] 表示该员工的基础绩效分，0 ≤ base[i] ≤ 10,000。

约束：

• 员工编号无重复、无遗漏。
• 整棵树为一棵合法的二叉树，有且仅有一个根节点。

输出描述

长度为 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]。

代码

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
const lines = [];

// 把所有输入行存进数组
rl.on('line', (line) => {
    lines.push(line.trim());
});
rl.on('close', (input) => {
    const n = Number(lines[0]);
    const left = lines[1].split(' ').map(Number);
    const right = lines[2].split(' ').map(Number);
    const base = lines[3].split(' ').map(Number);
    const hasParent = Array(n).fill(false);
    for(let i=0; i<=n; i++) {
        if(left[i] !== -1) {
            hasParent[left[i]] = true;
        }
        if (right[i] !== -1) {
            hasParent[right[i]] = true;
        }
    }
    const root = hasParent.findIndex(v => v === false);
    const ans = Array(n).fill(0);
    const dfs = (node) => {
        if (node === -1) return 0;
        dfs(left[node]);
        dfs(right[node]);
        ans[node] = base[node];
        if (left[node] !== -1) {
            ans[node] += ans[left[node]];
        }
        if (right[node] !== -1) {
            ans[node] +=  ans[right[node]];
        }
    }
    dfs(root);
    console.log(ans.join(','));
})