Operations on Tree — LeetCode 1993 Python Solution
MediumTreeDepth-First SearchBreadth-First SearchDesignArrayHash Table
- Problem
- #1993
- Pattern
- Tree Traversal
- Reading time
- 9 min
- Source
- leetcode.com
The problem
You are given a tree with n nodes numbered from 0 to n - 1 in the form of a parent array parent where parent[i] is the parent of the ith node. The root of the tree is node 0, so parent[0] = -1 since it has no parent.
Example
- Input
- ["LockingTree", "lock", "unlock", "unlock", "lock", "upgrade", "lock"]
- Output
- [null, true, false, true, true, true, false]
- Explanation
- LockingTree lockingTree = new LockingTree([-1, 0, 0, 1, 1, 2, 2]);
Python solution
Python
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)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1993. Operations on Tree is filed here because LeetCode tags it Tree, which is the vocabulary this hub collects.
The tree traversal guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 1993. Operations on Tree?
- LeetCode 1993. Operations on Tree is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1993. Operations on Tree?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1993. Operations on Tree?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1993. Operations on Tree cover?
- LeetCode 1993. Operations on Tree is tagged Tree, Depth-First Search, Breadth-First Search, Design, Array and Hash Table on LeetCode.