1993.树上的操作

链接：1993.树上的操作
难度：Medium
标签：树、深度优先搜索、广度优先搜索、设计、数组、哈希表
简介：给你一棵 n 个节点的树，编号从 0 到 n - 1 ，以父节点数组 parent 的形式给出，其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点，所以 parent[0] = -1 ，因为它没有父节点。你想要设计一个数据结构实现树里面对节点的加锁，解锁和升级操作。

题解 1 - python

• 编辑时间：2023-09-23
• 执行用时：52ms
• 内存消耗：15.61MB
• 编程语言：python
• 解法介绍：模拟。

class Node:
    def __init__(self, val: int):
        self.val = val
        self.parent = None
        self.children = []
        self.lock_state = 0
    def lock(self, user: int) -> bool:
        if self.lock_state:
            return False
        self.lock_state = user
        return True
    def unlock(self, user: int) -> bool:
        if self.lock_state != user:
            return False
        self.lock_state = 0
        return True
    def unlock_children(self) -> bool:
        for node in self.children:
            node.lock_state = 0
            node.unlock_children()
    def is_lock(self) -> bool:
        return self.lock_state != 0
    def is_parent_unlock(self) -> bool:
        return not self.parent or not self.parent.is_lock() and self.parent.is_parent_unlock()
    def exist_children_lock(self) -> bool:
        return any(child.is_lock() or child.exist_children_lock() for child in self.children)

class LockingTree:
    def __init__(self, parent: List[int]):
        self.nodes = [Node(i) for i in range(len(parent))]
        self.root = self.nodes[0]
        for i in range(1, len(parent)):
            self.nodes[i].parent = self.nodes[parent[i]]
            self.nodes[parent[i]].children.append(self.nodes[i])
    def lock(self, num: int, user: int) -> bool:
        return self.nodes[num].lock(user)
    def unlock(self, num: int, user: int) -> bool:
        return self.nodes[num].unlock(user)
    def upgrade(self, num: int, user: int) -> bool:
        node = self.nodes[num]
        if not node.is_lock() and node.is_parent_unlock() and node.exist_children_lock():
            node.lock(user)
            node.unlock_children()
            return True
        return False