10.力扣-樹-員工的重要性

力扣-樹-員工的重要性

員工的重要性（LeetCode 690）

• 題目概述：給定一個儲存員工資訊的資料結構，它包含了員工 唯一的 id ，重要度 和 直系下屬的 id 。比如，員工 1 是員工 2 的上司，員工 2 是員工 3 的上司。他們相應的重要度為 15 , 10 , 5 。那麼員工 1 的資料結構是 [1, 15, [2]] ，員工 2的 資料結構是 [2, 10, [3]] ，員工 3 的資料結構是 [3, 5, []] 。注意雖然員工 3 也是員工 1 的一個下屬，但是由于 并不是直系 下屬，是以沒有展現在員工 1 的資料結構中現在輸入一個公司的所有員工資訊，以及單個員工 id ，傳回這個員工和他所有下屬的重要度之和。
• 題目案例：

  

• 解題思路：員工管轄分布其實就是一個樹結構，而重要性就相當于該結點的value，而獲得value的方法就是将其子結點的value和自身自帶value相加，是以這道題本身就是一個周遊問題。是以也就有兩種解法：深度優先周遊和廣度優先周遊

  （這裡需要注意：題目所給員工是沒有管轄順序的，案例上是由順序，其實它的案例庫是有不按順序的，是以不要想着依據給的員工順序找周遊）

  解題關鍵：建立一個hashmap,鍵為員工編号，值為其對應的employee，這樣可以通過它的員工編号（id），順利找到他的importance和手下的子員工（我第一次做的時候值放的是importance，但是這樣很麻煩的是員工有誰還需要傳參數，不可取）

• 深度優先java代碼

//深度優先算法
class Solution1 {
    Map<Integer,Employee> hash=new HashMap<>();
    public int getImportance(List<Employee> employees, int id) {
        for(Employee employee:employees){
            hash.put(employee.id,employee);
        }
        return dfs(id);
    }
    public int dfs(int id){
        Employee employee=hash.get(id);
        int total=employee.importance;
        for(Integer num:employee.subordinates){
            total+=dfs(num);
        }
        return total;
    }
}

           

• 廣度優先java代碼

class Solution2 {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer,Employee> hash=new HashMap<>();
        for(Employee employee:employees){
            hash.put(employee.id,employee);
        }
        int total=0;
        Queue<Integer> queue=new LinkedList<>();
        queue.add(id);
        while(!queue.isEmpty()){
            int tempId=queue.poll();
            Employee employee=hash.get(tempId);
            total+=employee.importance;
            for(Integer num:employee.subordinates){
                queue.add(num);
            }
        }
        return total;
    }
}