Leetcode

Employee Importance

  • Time:O(n)
  • Space:O(n)

C++

class Solution {
 public:
  int getImportance(vector<Employee*> employees, int id) {
    unordered_map<int, Employee*> idToEmployee;

    for (Employee* employee : employees)
      idToEmployee[employee->id] = employee;

    return dfs(id, idToEmployee);
  }

 private:
  int dfs(int id, const unordered_map<int, Employee*>& idToEmployee) {
    int values = 0;

    for (const int subId : idToEmployee.at(id)->subordinates)
      values += dfs(subId, idToEmployee);

    return idToEmployee.at(id)->importance + values;
  }
};

JAVA

class Solution {
  public int getImportance(List<Employee> employees, int id) {
    Map<Integer, Employee> idToEmployee = new HashMap<>();

    for (Employee employee : employees)
      idToEmployee.put(employee.id, employee);

    return dfs(id, idToEmployee);
  }

  private int dfs(int id, Map<Integer, Employee> idToEmployee) {
    int values = 0;

    for (final int subId : idToEmployee.get(id).subordinates)
      values += dfs(subId, idToEmployee);

    return idToEmployee.get(id).importance + values;
  }
}

Python

class Solution:
  def getImportance(self, employees: List['Employee'], id: int) -> int:
    idToEmployee = {employee.id: employee for employee in employees}

    def dfs(id: int) -> int:
      values = idToEmployee[id].importance
      for subId in idToEmployee[id].subordinates:
        values += dfs(subId)
      return values

    return dfs(id)