主題
題目連結：
題目意譯：
你被給定一棵有著 n 個節點的樹，節點編號為 0 到 n - 1，以一個父母節點陣列 parent 之形式給定，其中 parent[i] 為第 i 個節點的父母節點。這棵樹的根節點為節點 0，因為其沒有父母節點因此 parent[0] = -1。你想要設計一個資料結構其可以支援使用著鎖定（lock）、解鎖（unlock）以及升級（upgrade）樹中的節點。
資料結構應支援以下函式：
Lock： 對於給定的使用者鎖定給定的節點，使得其他使用者無法鎖定同一個節點。你只能在一個節點已經解鎖的狀態下將其鎖定。
Unlock： 對於給定的使用者解鎖給定的節點。你只能在一個節點被同一個使用者鎖定的狀態下將其解鎖。
Upgrade： 對於給定的使用者鎖定給定的節點並將其所有後代節點全數解鎖。你只能在滿足以下三個條件的狀況下升級一個節點：
節點是解鎖的、
其至少有一個被鎖定的後代節點（對於任一使用者皆可），以及
其沒有任何被鎖定的祖先節點。
實作 LockingTree 類別：
LockingTree(int[] parent) 以 parent 陣列初始化資料結構。
lock(int num, int user) 回傳真（True）如果編號 user 的使用者可以把節點 num 鎖定；反之回傳假（False）。如果可以被鎖定的話，則該節點將變為被編號 user 的使用者鎖定之狀態。
unlock(int num, int user) 回傳真如果編號 user 的使用者可以把節點 num 解鎖；反之回傳假。如果可以被解鎖的話，則該節點將變為被解鎖的狀態。
upgrade(int num, int user) 回傳真如果編號 user 的使用者可以把節點 num 升級；反之回傳假。如果可以被升級的話，則該節點將會被升級。
限制：
n == parent.length
2 ≦ n ≦ 2000
0 ≦ parent[i] ≦ n - 1 對於 i ≠ 0
parent[0] == -1
0 ≦ num ≦ n - 1
1 ≦ user ≦ 10 ^ 4
parent 代表一棵合法的樹。
最多呼叫 lock 、 unlock 、 upgrade 總計 2000 次。
範例測資：
範例 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); // 回傳真因為節點 2 是解鎖的狀態。
// 節點 2 現在將被使用者 2 鎖定。
lockingTree.unlock(2, 3); // 回傳假因為使用者無法鎖定被使用者 2 鎖定的節點。
lockingTree.unlock(2, 2); // 回傳真因為節點 2 先前是被使用者 2 所鎖定的。
// 節點 2 現在將被解鎖。
lockingTree.lock(4, 5); // 回傳真因為節點 4 是解鎖的狀態。
// 節點 4 現在將被使用者 5 鎖定。
lockingTree.upgrade(0, 1); // 回傳真因為節點 0 是解鎖的狀態且有至少一個被鎖定的後代節點（節點 4）。
// 節點 0 現在將被使用者 1 鎖定且節點 4 現在將被解鎖。
lockingTree.lock(0, 1); // 回傳假因為節點 0 已經被鎖定了。
解題思維：
模擬即可。
利用一個陣列 L 來記錄每個節點是被誰鎖定的，如果無人鎖定則設為 -1。並利用 parent 陣列額外建立一個 children 陣列，其中 children[i] 是一個陣列，負責存節點 i 有幾個直接連接的子節點。
因此對於 lock 之操作，我們只要去檢查 L[num] 是不是已經有人鎖定這個節點了（也就是判斷 L[num] 是不是 -1）。如果有就回傳假。反之，將 L[num] 設為 user 並回傳真。
對於 unlock 之操作，檢查 L[num] 是否等於 user。如果不是就回傳假。反之，將 L[num] 設為 -1 並回傳真。
對於 upgrade，我們先檢查 L[num] 是否為 -1。如果是就回傳假。不是則再利用一次的深度優先搜尋（Depth First Search，DFS）去 children[num] 找出所有後代節點是否至少有一個節點是被鎖定的。如果沒有則回傳假。如果有就在利用 parent 進行另一次的深度優先搜尋，去找是否所有祖先節點都是解鎖的狀態。如果不是就回傳假。反之，此時我們才能將節點鎖定（L[num] 設為 user），然後再跑最後一次深度優先搜尋把所有後代節點解鎖並回傳真。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
