532. Twin Subtrees
A folder template is stored as a binary tree root, where every node is a folder labelled with an integer and has at most a left and a right sub-folder. Two sub-trees are twins when they have exactly the same shape and the same label at every matching position. A sub-tree is a node together with all of its descendants, and a single leaf counts as a sub-tree. Find every sub-tree that has at least one twin elsewhere in the tree and return the root node of one sub-tree from each group of twins, so each group of identical sub-trees contributes exactly one entry. The entries may be returned in any order. If nothing is duplicated, or the tree is empty, return an empty list.
Example 1
- Input:
- root = [7,3,3,5,null,5,9]
- Output:
- [[5]]
- Explanation:
The leaf 5 appears twice, while 3(5) and 3(5,9) differ, so only the leaf 5 is reported.
Example 2
- Input:
- root = [8,4,4,2,6,2,6]
- Output:
- [[2],[6],[4,2,6]]
- Explanation:
The leaves 2 and 6 and the sub-tree 4(2,6) each appear twice, so one root per group is returned.
Example 3
- Input:
- root = [9,5,12,null,7]
- Output:
- []
- Explanation:
All sub-trees are different, so the result is empty.
Constraints
0 ≤ number of nodes ≤ 500
-1000 ≤ Node.val ≤ 1000
How this problem is judged
- Answers
- The outer list may be in any order. Everything inside each item must match exactly.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)