1993. 树上的操作

Medium

题目描述

给你一棵 n 个节点的树，节点编号从 0 到 n - 1，以父节点数组 parent 的形式给出，其中 parent[i] 是第 i 个节点的父节点。树的根节点是节点 0，所以 parent[0] = -1，因为它没有父节点。你想要设计一个数据结构，允许用户锁定、解锁和升级树中的节点。

数据结构应该支持以下函数：

锁定：给指定用户锁定指定节点，并防止其他用户锁定同一节点。只有当节点未锁定时，你才能使用此函数锁定节点。
解锁：给指定用户解锁指定节点。只有当节点当前被同一用户锁定时，你才能使用此函数解锁节点。
升级：给指定用户锁定指定节点，并解锁它的所有后代，无论是谁锁定的。只有如果满足下述 3 个条件，你才能升级节点：
- 指定节点当前状态为未锁定
- 指定节点至少有一个锁定状态的后代（任何用户）
- 指定节点没有任何锁定的祖先

实现 LockingTree 类：

LockingTree(int[] parent) 用父节点数组初始化数据结构
lock(int num, int user) 如果 id 为 user 的用户能够锁定节点 num，则返回 true，否则返回 false。如果可以，节点 num 会被用户 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 <= 10^4
parent 表示一棵有效的树
lock、unlock 和 upgrade 总共最多被调用 2000 次

解题思路

这道题需要实现一个支持树节点锁定、解锁和升级操作的数据结构。核心思路如下：

数据结构设计：

使用邻接表存储每个节点的子节点，便于遍历后代
使用数组记录每个节点的锁定状态和锁定用户
保存父节点数组用于向上遍历祖先

操作实现：

Lock操作：检查节点是否未锁定，如果是则锁定并返回true
Unlock操作：检查节点是否被指定用户锁定，如果是则解锁并返回true
Upgrade操作最为复杂，需要满足三个条件：
- 节点未锁定
- 至少有一个锁定的后代（使用DFS遍历）
- 没有锁定的祖先（向上遍历到根节点检查）
如果条件满足，则锁定当前节点并解锁所有后代

优化策略：

由于约束较小（n ≤ 2000），可以直接使用DFS遍历，无需额外的优化
在upgrade操作中，先检查条件再执行操作，避免无效的状态修改

时间复杂度主要由upgrade操作决定，需要遍历所有后代和祖先。

代码实现

class LockingTree {
private:
    vector<vector<int>> children;
    vector<int> parent;
    vector<int> locked; // 0表示未锁定，>0表示锁定的用户ID
    
    bool hasLockedDescendant(int node) {
        for (int child : children[node]) {
            if (locked[child] > 0 || hasLockedDescendant(child)) {
                return true;
            }
        }
        return false;
    }
    
    void unlockDescendants(int node) {
        locked[node] = 0;
        for (int child : children[node]) {
            unlockDescendants(child);
        }
    }
    
    bool hasLockedAncestor(int node) {
        int curr = parent[node];
        while (curr != -1) {
            if (locked[curr] > 0) {
                return true;
            }
            curr = parent[curr];
        }
        return false;
    }
    
public:
    LockingTree(vector<int>& parent) : parent(parent) {
        int n = parent.size();
        children.resize(n);
        locked.resize(n, 0);
        
        for (int i = 1; i < n; i++) {
            children[parent[i]].push_back(i);
        }
    }
    
    bool lock(int num, int user) {
        if (locked[num] == 0) {
            locked[num] = user;
            return true;
        }
        return false;
    }
    
    bool unlock(int num, int user) {
        if (locked[num] == user) {
            locked[num] = 0;
            return true;
        }
        return false;
    }
    
    bool upgrade(int num, int user) {
        if (locked[num] == 0 && hasLockedDescendant(num) && !hasLockedAncestor(num)) {
            locked[num] = user;
            for (int child : children[num]) {
                unlockDescendants(child);
            }
            return true;
        }
        return false;
    }
};

class LockingTree:

    def __init__(self, parent: List[int]):
        self.parent = parent
        self.locked = [0] * len(parent)  # 0表示未锁定，>0表示锁定的用户ID
        self.children = [[] for _ in range(len(parent))]
        
        for i in range(1, len(parent)):
            self.children[parent[i]].append(i)
    
    def _has_locked_descendant(self, node: int) -> bool:
        for child in self.children[node]:
            if self.locked[child] > 0 or self._has_locked_descendant(child):
                return True
        return False
    
    def _unlock_descendants(self, node: int) -> None:
        self.locked[node] = 0
        for child in self.children[node]:
            self._unlock_descendants(child)
    
    def _has_locked_ancestor(self, node: int) -> bool:
        curr = self.parent[node]
        while curr != -1:
            if self.locked[curr] > 0:
                return True
            curr = self.parent[curr]
        return False

    def lock(self, num: int, user: int) -> bool:
        if self.locked[num] == 0:
            self.locked[num] = user
            return True
        return False

    def unlock(self, num: int, user: int) -> bool:
        if self.locked[num] == user:
            self.locked[num] = 0
            return True
        return False

    def upgrade(self, num: int, user: int) -> bool:
        if (self.locked[num] == 0 and 
            self._has_locked_descendant(num) and 
            not self._has_locked_ancestor(num)):
            self.locked[num] = user
            for child in self.children[num]:
                self._unlock_descendants(child)
            return True
        return False

public class LockingTree {
    private List<int>[] children;
    private int[] parent;
    private int[] locked; // 0表示未锁定，>0表示锁定的用户ID
    
    public LockingTree(int[] parent) {
        this.parent = parent;
        int n = parent.Length;
        children = new List<int>[n];
        locked = new int[n];
        
        for (int i = 0; i < n; i++) {
            children[i] = new List<int>();
        }
        
        for (int i = 1; i < n; i++) {
            children[parent[i]].Add(i);
        }
    }
    
    private bool HasLockedDescendant(int node) {
        foreach (int child in children[node]) {
            if (locked[child] > 0 || HasLockedDescendant(child)) {
                return true;
            }
        }
        return false;
    }
    
    private void UnlockDescendants(int node) {
        locked[node] = 0;
        foreach (int child in children[node]) {
            UnlockDescendants(child);
        }
    }
    
    private bool HasLockedAncestor(int node) {
        int curr = parent[node];
        while (curr != -1) {
            if (locked[curr] > 0) {
                return true;
            }
            curr = parent[curr];
        }
        return false;
    }
    
    public bool Lock(int num, int user) {
        if (locked[num] == 0) {
            locked[num] = user;
            return true;
        }
        return false;
    }
    
    public bool Unlock(int num, int user) {
        if (locked[num] == user) {
            locked[num] = 0;
            return true;
        }
        return false;
    }
    
    public bool Upgrade(int num, int user) {
        if (locked[num] == 0 && HasLockedDescendant(num) && !HasLockedAncestor(num)) {
            locked[num] = user;
            foreach (int child in children[num]) {
                UnlockDescendants(child);
            }
            return true;
        }
        return false;
    }
}

var LockingTree = function(parent) {
    this.parent = parent;
    this.locked = new Array(parent.length).fill(0); // 0表示未锁定，>0表示锁定的用户ID
    this.children = Array.from({length: parent.length}, () => []);
    
    for (let i = 1; i < parent.length; i++) {
        this.children[parent[i]].push(i);
    }
};

LockingTree.prototype.hasLockedDescendant = function(node) {
    for (let child of this.children[node]) {
        if (this.locked[child] > 0 || this.hasLockedDescendant(child)) {
            return true;
        }
    }
    return false;
};

LockingTree.prototype.unlockDescendants = function(node) {
    this.locked[node] = 0;
    for (let child of this.children[node]) {
        this.unlockDescendants(child);
    }
};

LockingTree.prototype.hasLockedAncestor = function(node) {
    let curr = this.parent[node];
    while (curr !== -1) {
        if (this.locked[curr] > 0) {
            return true;
        }
        curr = this.parent[curr];
    }
    return false;
};

LockingTree.prototype.lock = function(num, user) {
    if (this.locked[num]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(n)	O(n)
lock	O(1)	O(1)
unlock	O(1)	O(1)
upgrade	O(n)	O(h)

其中 n 是节点数量，h 是树的高度。

题目描述#

解题思路#

代码实现#

复杂度分析#

相关题目#

题目描述

解题思路

代码实现

复杂度分析

相关题目