树上的操作【LC1993】
给你一棵
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
会被 升级 。
-
思路
使用数组记录每个节点的父节点以及上锁状态,并使用list记录每个节点的孩子节点,方便dfs操作
- lock和unlock函数进行简单判断即可
- upgrade函数需要判断祖先节点是否上锁,再通过dfs判断是否有上锁的孩子节点,并将其解锁
-
实现
class LockingTree { // 记录每个节点的根节点以及加锁状态 int[] locked; int[] parent; int n; List<Integer>[] children; public LockingTree(int[] parent) { this.n = parent.length; this.parent = parent; this.locked = new int[n]; this.children = new List[n]; Arrays.fill(locked, -1); Arrays.setAll(children, e -> new ArrayList<>()); for (int i = 0; i < n; i++){ if (parent[i] != -1){ children[parent[i]].add(i); } } } public boolean lock(int num, int user) { if (locked[num] != -1) return false; locked[num] = user; return true; } public boolean unlock(int num, int user) { if (locked[num] == user){ locked[num] = -1; return true; } return false; } public boolean upgrade(int num, int user) { if (locked[num] != -1) return false; // 判断祖先节点是否上锁 int p = parent[num]; while (p != -1){ if (locked[p] != -1) return false; p = parent[p]; } // 判断是否有子孙节点加锁了,并给子孙节点解锁 boolean[] res = {false}; dfs(num, res); if (res[0] == false) return false; locked[num] = user; return true; } public void dfs(int p, boolean[] lock){ for (int u : children[p]){ if (locked[u] != -1){ lock[0] = true; locked[u] = -1; } dfs(u, lock); } } } /** * 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); */
- 复杂度
- 时间复杂度: n n n为二叉树的节点数目,lock和unlock为 O ( n ) \mathcal{O}(n) O(n),upgrade为 O ( 1 ) \mathcal{O}(1) O(1)
- 空间复杂度: O ( n ) \mathcal{O}(n) O(n)
- 复杂度