What is the primary pattern for solving the 'Operations on Tree' problem?

The key pattern is array scanning combined with hash lookups to efficiently manage node states in a tree structure.

How do we ensure efficient upgrades in the tree?

Use the parent array for quick traversal and a hash table to track locked nodes, enabling fast upgrades.

What should be the time complexity for lock/unlock operations?

Both `lock` and `unlock` operations should run in O(1) time using hash lookups.

How does the parent array contribute to solving this problem?

The parent array provides an efficient way to traverse the tree, helping manage the upgrade logic and track parent-child relationships.

Can the 'Operations on Tree' problem be optimized for larger inputs?

Yes, optimizing the tree traversal for upgrades and ensuring minimal memory usage can make the solution scalable to large inputs.

#1993

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

树上的操作

给你一棵 n 个节点的树，编号从 0 到 n - 1 ，以父节点数组 parent 的形式给出，其中 parent[i] 是第 i 个节点的父节点。树的根节点为 0 号节点，所以 parent[0] = -1 ，因为它没有父节点。你想要设计一个数据结构实现树里面对节点的加锁，解锁和升级操作。数据结…

数组哈希表树深度优先搜索广度优先搜索

题目描述

给你一棵 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 会被升级。

示例 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⁴
parent 表示一棵合法的树。
lock ，unlock 和 upgrade 的调用总共不超过 2000 次。

lightbulb

解题思路

方法一：DFS

我们定义以下几个变量：

$locked$ ：记录每个节点的锁定状态，其中 $locked[i]$ 表示节点 $i$ 的锁定状态，如果节点 $i$ 未被上锁，则 $locked[i] = -1$ ，否则 $locked[i]$ 为锁定节点 $i$ 的用户编号。
$parent$ ：记录每个节点的父节点。
$children$ ：记录每个节点的子节点。

调用 $lock$ 函数时，如果节点 $num$ 未被上锁，则将节点 $num$ 上锁，返回 true，否则返回 false。

调用 $unlock$ 函数时，如果节点 $num$ 被上锁且上锁的用户编号为 $user$ ，则将节点 $num$ 解锁，返回 true，否则返回 false。

调用 $upgrade$ 函数时，我们首先判断节点 $num$ 及其祖先节点是否被上锁，如果是，则返回 $false$ 。否则，我们判断节点 $num$ 的子孙节点是否有被上锁的，如果没有，则返回 false。否则，我们将节点 $num$ 及其子孙节点解锁，然后将节点 $num$ 上锁，返回 true。

时间复杂度方面，初始化和 $upgrade$ 函数的时间复杂度均为 $O(n)$ ，而 $lock$ 和 $unlock$ 函数的时间复杂度均为 $O(1)$ 。空间复杂度 $O(n)$ 。其中 $n$ 是节点的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

class LockingTree:
    def __init__(self, parent: List[int]):
        n = len(parent)
        self.locked = [-1] * n
        self.parent = parent
        self.children = [[] for _ in range(n)]
        for son, fa in enumerate(parent[1:], 1):
            self.children[fa].append(son)

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

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

    def upgrade(self, num: int, user: int) -> bool:
        def dfs(x: int):
            nonlocal find
            for y in self.children[x]:
                if self.locked[y] != -1:
                    self.locked[y] = -1
                    find = True
                dfs(y)

        x = num
        while x != -1:
            if self.locked[x] != -1:
                return False
            x = self.parent[x]

        find = False
        dfs(num)
        if not find:
            return False
        self.locked[num] = user
        return True


# Your LockingTree object will be instantiated and called as such:
# obj = LockingTree(parent)
# param_1 = obj.lock(num,user)
# param_2 = obj.unlock(num,user)
# param_3 = obj.upgrade(num,user)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate efficiently designs data structures for dynamic operations on trees.
question_mark
Look for clear explanations of array and hash table usage to manage state.
question_mark
Focus on the trade-off between tree traversal and hash lookups for optimized performance.

warning

常见陷阱

外企场景

error
Overcomplicating the tree traversal logic during upgrade operations.
error
Incorrectly handling lock/unlock state changes across multiple users.
error
Not considering edge cases, such as trying to unlock a node locked by another user.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Add a query function to check if a node is locked.
arrow_right_alt
Allow multiple users to lock the same node with different states.
arrow_right_alt
Optimize for memory usage by using a more compact data structure for large trees.

help

常见问题

外企场景

继续练习

#2368 受限条件下可到达节点的数目 #1261 在受污染的二叉树中查找元素 #690 员工的重要性