給你一棵 n 個節點的樹，編號從 0 到 n - 1 ，以父節點數組 parent 的形式給出，其中 parent[i] 是第 i 個節點的父節點。樹的根節點為 0 號節點，所以 parent[0] = -1 ，因為它沒有父節點。你想要設計一個數據結構實現樹里面對節點的加鎖，解鎖和升級操作。
數據結構需要支持如下函數：
- Lock：指定用戶給指定節點 上鎖 ，上鎖后其他用戶將無法給同一節點上鎖。只有當節點處于未上鎖的狀態下，才能進行上鎖操作。
- Unlock：指定用戶給指定節點 解鎖 ，只有當指定節點當前正被指定用戶鎖住時，才能執行該解鎖操作。
- Upgrade：指定用戶給指定節點 上鎖 ，并且將該節點的所有子孫節點 解鎖 。只有如下 3 個條件 全部 滿足時才能執行升級操作：
- 指定節點當前狀態為未上鎖。
- 指定節點至少有一個上鎖狀態的子孫節點（可以是 任意 用戶上鎖的）。
- 指定節點沒有任何上鎖的祖先節點。
請你實現 LockingTree 類：
LockingTree(int[] parent) 用父節點數組初始化數據結構。
lock(int num, int user) 如果 id 為 user 的用戶可以給節點 num 上鎖，那么返回 true ，否則返回 false 。如果可以執行此操作，節點 num 會被 id 為 user 的用戶 上鎖 。
unlock(int num, int user) 如果 id 為 user 的用戶可以給節點 num 解鎖，那么返回 true ，否則返回 false 。如果可以執行此操作，節點 num 變為 未上鎖 狀態。
upgrade(int num, int user) 如果 id 為 user 的用戶可以給節點 num 升級，那么返回 true ，否則返回 false 。如果可以執行此操作，節點 num 會被 升級 。
示例 1：
輸入：
["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"]
[[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]]
輸出：
[null, true, false, true, true, true, false]解釋：
LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);
lockingTree.lock(2, 2); // 返回 true ，因為節點 2 未上鎖。// 節點 2 被用戶 2 上鎖。
lockingTree.unlock(2, 3); // 返回 false ，因為用戶 3 無法解鎖被用戶 2 上鎖的節點。
lockingTree.unlock(2, 2); // 返回 true ，因為節點 2 之前被用戶 2 上鎖。// 節點 2 現在變為未上鎖狀態。
lockingTree.lock(4, 5); // 返回 true ，因為節點 4 未上鎖。// 節點 4 被用戶 5 上鎖。
lockingTree.upgrade(0, 1); // 返回 true ，因為節點 0 未上鎖且至少有一個被上鎖的子孫節點（節點 4）。// 節點 0 被用戶 1 上鎖，節點 4 變為未上鎖。
lockingTree.lock(0, 1); // 返回 false ，因為節點 0 已經被上鎖了。
提示：
- n == parent.length
- 2 <= n <= 2000
- 對于 i != 0 ，滿足 0 <= parent[i] <= n - 1
- parent[0] == -1
- 0 <= num <= n - 1
- 1 <= user <= 104
- parent 表示一棵合法的樹。
- lock ，unlock 和 upgrade 的調用 總共 不超過 2000 次。
解題思路
使用map維護被鎖節點和加鎖者的關系，再使用一個map維護父節點和對應子節點之間的關系
lock
判斷是否有鎖，如果沒有，則可以直接加鎖
unlock
判斷當前鎖的加鎖者是否為自己
upgrade
- 先向上遍歷祖先節點和加鎖節點，判斷是否有加鎖
- 再遍歷子孫節點，判斷是否加鎖
- 給所有子孫節點解鎖，給當前節點加鎖
代碼
class LockingTree {int[] p;Map<Integer, Integer> locked = new HashMap<>();Map<Integer,Set<Integer>> child=new HashMap<>();public LockingTree(int[] parent) {p = parent;for (int i = 0; i < parent.length; i++) {if (!child.containsKey(p[i]))child.put(p[i],new HashSet<>());child.get(p[i]).add(i);}}public boolean lock(int num, int user) {if (locked.containsKey(num) )return false;locked.put(num, user);return true;}public boolean unlock(int num, int user) {if (locked.containsKey(num) && locked.get(num) == user) {locked.remove(num);return true;} else return false;}public boolean dfs(int num) {while (num!=-1){if(locked.containsKey(num))return false;num=p[num];}return true;}public boolean ddfs(int num,int f) {if (locked.containsKey(num)&&num!=f){return true;}boolean res=false;if (child.containsKey(num)){for (Integer integer : child.get(num)) {res|=ddfs(integer,f);}}return res;}public void dddfs(int num) {locked.remove(num);if (child.containsKey(num)){for (Integer integer : child.get(num)) {dddfs(integer);}}}public boolean upgrade(int num, int user) {if (dfs(num)&&ddfs(num,num)){dddfs(num);locked.put(num, user);return true;}return false;}}/*** Your LockingTree object will be instantiated and called as such:* LockingTree obj = new LockingTree(parent);* boolean param_1 = obj.lock(num,user);* boolean param_2 = obj.unlock(num,user);* boolean param_3 = obj.upgrade(num,user);*//*** Your LockingTree object will be instantiated and called as such:* LockingTree obj = new LockingTree(parent);* boolean param_1 = obj.lock(num,user);* boolean param_2 = obj.unlock(num,user);* boolean param_3 = obj.upgrade(num,user);*/
