部门绩效汇总[200分]

题目内容

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

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

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

输入描述

共有 4 个输入参数：

• $n$：员工总数（$1 \le n \le 1000$），编号 $0$ 到 $n-1$。
• $left$：长度为 $n$ 的整数数组，$left[i]$ 表示其左下属的编号，$-1$ 表示无。
• $right$：长度为 $n$ 的整数数组，$right[i]$ 表示其右下属的编号，$-1$ 表示无。
• $base$：长度为 $n$ 的整数数组，$base[i]$ 表示该员工的基础绩效分，$0 \le base[i] \le 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(','));
})