906. Find Duplicate Subtrees

Given the root of a binary tree, a duplicate subtree is a subtree structure (same shape and same node values) that appears in two or more places. Return the number of distinct duplicate subtree structures (count each repeated structure once, regardless of how many times it repeats). The tree is given as a level-order array.

Input: A level-order array of the tree.

Output: Integer — the count of distinct duplicate subtrees.

Examples

Input: [1,2,3,4,null,2,4,null,null,4]
Output: 2
Explanation: The subtree '4' and the subtree '2->4' each repeat.

Input: [2,1,1]
Output: 1
Explanation: The leaf '1' repeats.

Input: [1,2,3]
Output: 0
Explanation: No duplicates.

Constraints

• 1<=nodes<=5000
• -200<=value<=200

Asked by