NeetCode #453LC-1993MediumTrees
← Back to All Problems#453 · #1993 · Operations on Tree(树上的操作)
📌 Problem Statement & Constraints
Design a locking tree with
n nodes numbered 0..n-1 and a parent array (parent[i] is the parent of i, -1 for the root). Implement lock(num, user), unlock(num, user) and upgrade(num, user). upgrade succeeds only when the node is unlocked, no ancestor is locked, and at least one descendant is locked; it then unlocks all locked descendants and locks the node. Constraints: 1 <= n <= 2000; at most 2000 calls.💡 Core Algorithmic Approaches
- Keep a
lockedarray mapping each node to the locking user, or 0 for unlocked. lockandunlockare O(1) checks against that array.upgradeneeds two traversals: walk up theparentchain to verify no locked ancestor, and walk down the children to collect locked descendants.- A children adjacency list makes the downward walk efficient; the descendant unlocks happen during that walk.
💻 Benchmark Python3 Implementation
class LockingTree:
def __init__(self, parent: List[int]):
from collections import defaultdict
self.parent = parent
self.locked = [0] * len(parent) # node -> user, 0 means unlocked
self.children = defaultdict(list)
for i, p in enumerate(parent):
if p != -1:
self.children[p].append(i)
def lock(self, num: int, user: int) -> bool:
if self.locked[num]:
return False
self.locked[num] = user
return True
def unlock(self, num: int, user: int) -> bool:
if self.locked[num] != user:
return False # only the locker may unlock
self.locked[num] = 0
return True
def upgrade(self, num: int, user: int) -> bool:
if self.locked[num]:
return False # must be unlocked
# 1) no locked ancestor
p = self.parent[num]
while p != -1:
if self.locked[p]:
return False
p = self.parent[p]
# 2) at least one locked descendant, and unlock them all
found = False
st = list(self.children[num])
while st:
c = st.pop()
if self.locked[c]:
self.locked[c] = 0
found = True
st.extend(self.children[c])
if not found:
return False # nothing to upgrade from
self.locked[num] = user
return True⚡ Complexity Deep Dive
⏱️ Time Complexity
O(depth) for lock/unlock, O(n) for upgrade in the worst case.
💾 Space Complexity
O(n) for the locked array and the adjacency list.
⚠️ Interview Pitfalls & Follow-ups
- Unlocking descendants before confirming the upgrade: the ancestor check must pass first, and the descendant scan must find at least one locked node; otherwise the unlocks would corrupt the state.
- Allowing the locker's identity to be ignored in
unlock: only the user who locked a node may unlock it. - Checking only the immediate parent: the whole ancestor chain must be free.
- Forgetting to lock the node itself after a successful upgrade: the operation both unlocks descendants and locks the node.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.