#1719
Number Of Ways To Reconstruct A Tree
candidate master · 1590 · lc hard +32 · verified · 45.6% accepted · 235 likes · top 29%
Description
You are given an array pairs where pairs[i] = [xi, yi] (no duplicates, xi < yi). Let ways be the number of rooted trees where every node value appears in pairs and [xi, yi] is in pairs iff one is an ancestor of the other. Return 0 if ways == 0, 1 if ways == 1, or 2 if ways > 1.
Example 1:
Input: pairs = [[1,2],[2,3]]
Output: 1
Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
Example 2:
Input: pairs = [[1,2],[2,3],[1,3]]
Output: 2
Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
Example 3:
Input: pairs = [[1,2],[2,3],[2,4],[1,5]]
Output: 0
Explanation: There are no valid rooted trees.
Code
1
2
3