Number Of Ways To Reconstruct A Tree — LeetCode 1719 Python Solution
HardTreeGraph
- Problem
- #1719
- Pattern
- Tree Traversal
- Reading time
- 6 min
- Source
- leetcode.com
The problem
You are given an array pairs, where pairs[i] = [xi, yi], and: There are no duplicates. xi < yi Let ways be the number of rooted trees that satisfy the following conditions: The tree consists of nodes whose values appeared in pairs.
Example
- Input
- pairs = [[1,2],[2,3]]
- Output
- 1
- Explanation
- There is exactly one valid rooted tree, which is shown in the above figure.
Python solution
Python
class Solution:
def checkWays(self, pairs: List[List[int]]) -> int:
g = [[False] * 510 for _ in range(510)]
v = defaultdict(list)
for x, y in pairs:
g[x][y] = g[y][x] = True
v[x].append(y)
v[y].append(x)
nodes = []
for i in range(510):
if v[i]:
nodes.append(i)
g[i][i] = True
nodes.sort(key=lambda x: len(v[x]))
equal = False
root = 0
for i, x in enumerate(nodes):
j = i + 1
while j < len(nodes) and not g[x][nodes[j]]:
j += 1
if j < len(nodes):
y = nodes[j]
if len(v[x]) == len(v[y]):
equal = True
for z in v[x]:
if not g[y][z]:
return 0
else:
root += 1
if root > 1:
return 0
return 2 if equal else 1Complexity
| Measure | Complexity |
|---|---|
| Time | O(V+E) |
| Space | O(V) auxiliary |
Pattern: Tree Traversal
Choose the order — preorder, inorder, postorder, level — and the problem solves itself. LeetCode 1719. Number Of Ways To Reconstruct A 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
LeetCode 1361Validate Binary Tree NodesMediumLeetCode 1377Frog Position After T SecondsHardLeetCode 2246Longest Path With Different Adjacent CharactersHardLeetCode 2467Most Profitable Path in a TreeMediumLeetCode 2477Minimum Fuel Cost to Report to the CapitalMediumLeetCode 2603Collect Coins in a TreeHard
Frequently asked questions
- How hard is LeetCode 1719. Number Of Ways To Reconstruct A Tree?
- LeetCode 1719. Number Of Ways To Reconstruct A Tree is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1719. Number Of Ways To Reconstruct A Tree?
- The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1719. Number Of Ways To Reconstruct A Tree?
- The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1719. Number Of Ways To Reconstruct A Tree cover?
- LeetCode 1719. Number Of Ways To Reconstruct A Tree is tagged Tree and Graph on LeetCode.