1649. Twin Family Shapes
Two family trees each describe n people numbered 0 to n-1, and in both of them person 0 is the founder. The parent-child links of the first tree are given in edgesA and those of the second in edgesB, as pairs [u, v] in no particular direction; each list has n-1 pairs and forms a tree.
Two such trees have the same family shape if you can pair up the people of one tree with the people of the other so that the founders are paired and every parent-child link is matched by a parent-child link. The order in which children are listed is irrelevant, and the numbering of people may differ between the trees. Return true if the shapes are the same and false otherwise.
Aim for O(n log n) time and O(n) space, and avoid deep recursion because a tree can be a chain.
Example 1
- Input:
- n = 5edgesA = [[0,1],[0,2],[2,3],[2,4]]edgesB = [[0,3],[3,1],[0,2],[3,4]]
- Output:
- true
- Explanation:
Both trees have a root with a leaf child and a child that has two leaf children, so the shapes match.
Example 2
- Input:
- n = 4edgesA = [[0,1],[1,2],[2,3]]edgesB = [[1,0],[1,2],[1,3]]
- Output:
- false
- Explanation:
The first tree is a chain hanging from the root; in the second the root has a single child with two leaf children, so they differ.
Constraints
1 ≤ n ≤ 2000
edgesA and edgesB each have n - 1 pairs [u, v] with 0 ≤ u, v < n and form a tree rooted at node 0
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)