966. Find Duplicate Subtrees (Hashing)

Given the root of a binary tree, a duplicate subtree is a subtree structure (identical shape and node values) appearing two or more times. Return the number of distinct duplicate subtree structures (each repeated structure counted once). 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: Subtree '4' and 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<=10^4
• -200<=value<=200

Asked by