Google VO 面试真题解析：Now That You’ve Identified Underpaid Managers｜树形 DFS / 后序遍历

Given a company tree, calculate how many managers are paid less than the average salary of their direct and indirect employees?

For example, consider the following:

A($100)
|
+- B($100)
+- C($200)
   |
   +- D($60)

Here there are two managers, A and C. A should be counted since the average salary of their employees is ($100 + $200 + $60) / 3 = $120, which is more than $100. C should not be counted because their salary is $200, which is more than the average salary of their employees, that is $60.

Followup question: Now that you’ve identified underpaid managers, we want to make sure that they are paid fairly. Given an org tree, find out the minimum amount of extra salary needed to make sure that no one is underpaid.

这道题给出一棵公司组织树，要求统计有多少个经理的薪资低于其所有直接和间接下属的平均薪资。核心做法通常是对树做后序 DFS：先递归统计每个子树的员工总薪资和人数，再回到当前经理节点时计算其下属平均值并判断是否“被低估”。示例中需要注意的是，比较对象是该经理的所有后代员工，而不是直接下属。Follow-up 则进一步要求在组织树上做自底向上的动态规划 / 贪心统计，计算让所有人都不再低薪所需的最小补薪总额。