1993. Operations On Tree

Medium

Description

設計一個支援鎖定、解鎖和升級操作的樹結構。Lock 鎖定節點給指定使用者；Unlock 解鎖節點（需同一使用者）；Upgrade 鎖定節點並解鎖所有子孫節點（需節點未鎖定、至少一個子孫被鎖定、所有祖先未鎖定）。

Example:

Input: [“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]] Output: [null,true,false,true,true,true,false]

Intuition#

模擬題，關鍵在 upgrade 操作需要檢查祖先鏈和子孫樹。

Lock / Unlock 操作簡單，用陣列記錄每個節點被哪個使用者鎖定
Upgrade 需要三個檢查：自身未鎖定、所有祖先未鎖定、至少一個子孫被鎖定
用 parent 陣列往上檢查祖先，用鄰接表往下 DFS 檢查子孫

Approaches#

1: 直接模擬#

概念: 用陣列記錄鎖定狀態，Lock/Unlock 直接操作，Upgrade 逐一檢查條件
時間複雜度: Lock/Unlock O(1)，Upgrade O(n)
空間複雜度: O(n)

class LockingTree(parent: IntArray) {
    private val par = parent
    private val children = Array(parent.size) { mutableListOf<Int>() }
    private val lockedBy = IntArray(parent.size) { -1 } // -1 表示未鎖定

    init {
        for (i in 1 until parent.size) {
            children[parent[i]].add(i)
        }
    }

    fun lock(num: Int, user: Int): Boolean {
        if (lockedBy[num] != -1) return false
        lockedBy[num] = user
        return true
    }

    fun unlock(num: Int, user: Int): Boolean {
        if (lockedBy[num] != user) return false
        lockedBy[num] = -1
        return true
    }

    fun upgrade(num: Int, user: Int): Boolean {
        // 條件 1: 自身未鎖定
        if (lockedBy[num] != -1) return false
        // 條件 2: 所有祖先未鎖定
        var ancestor = par[num]
        while (ancestor != -1) {
            if (lockedBy[ancestor] != -1) return false
            ancestor = par[ancestor]
        }
        // 條件 3: 至少一個子孫被鎖定，並解鎖所有子孫
        if (!unlockDescendants(num)) return false
        // 鎖定當前節點
        lockedBy[num] = user
        return true
    }

    // 解鎖所有子孫，回傳是否至少有一個被鎖定的子孫
    private fun unlockDescendants(node: Int): Boolean {
        var found = false
        for (child in children[node]) {
            if (lockedBy[child] != -1) {
                lockedBy[child] = -1
                found = true
            }
            if (unlockDescendants(child)) found = true
        }
        return found
    }
}

⭐ 2: 優化祖先檢查（相同思路，清晰實作）#

概念: 與方法 1 相同，但將三個條件的檢查抽成獨立函數，提高可讀性
時間複雜度: Lock/Unlock O(1)，Upgrade O(n)
空間複雜度: O(n)

class LockingTree(parent: IntArray) {
    private val par = parent
    private val children = Array(parent.size) { mutableListOf<Int>() }
    private val lockedBy = IntArray(parent.size) { -1 }

    init {
        for (i in 1 until parent.size) {
            children[parent[i]].add(i)
        }
    }

    fun lock(num: Int, user: Int): Boolean {
        if (lockedBy[num] != -1) return false
        lockedBy[num] = user
        return true
    }

    fun unlock(num: Int, user: Int): Boolean {
        if (lockedBy[num] != user) return false
        lockedBy[num] = -1
        return true
    }

    fun upgrade(num: Int, user: Int): Boolean {
        if (lockedBy[num] != -1) return false
        if (hasLockedAncestor(num)) return false
        if (!hasLockedDescendant(num)) return false
        unlockAllDescendants(num)
        lockedBy[num] = user
        return true
    }

    private fun hasLockedAncestor(node: Int): Boolean {
        var curr = par[node]
        while (curr != -1) {
            if (lockedBy[curr] != -1) return true
            curr = par[curr]
        }
        return false
    }

    private fun hasLockedDescendant(node: Int): Boolean {
        for (child in children[node]) {
            if (lockedBy[child] != -1) return true
            if (hasLockedDescendant(child)) return true
        }
        return false
    }

    private fun unlockAllDescendants(node: Int) {
        for (child in children[node]) {
            lockedBy[child] = -1
            unlockAllDescendants(child)
        }
    }
}

🔑 Takeaways#

Pattern: 設計題，樹上的鎖定機制需要同時往上（祖先）和往下（子孫）檢查
關鍵技巧: 用 parent 陣列向上遍歷、鄰接表向下 DFS，是樹結構設計題的常見搭配