Description
Given the root of a binary tree, return all duplicate subtrees. For each duplicate, return the root node of any one of them.
Examples
Input:
root = [1,2,3,4,null,2,4,null,null,4]Output:
[[2,4],[4]]Explanation:
Two duplicate subtrees.
Input:
root = [5,3,8,3,null,8,null,null,null,null,null]Output:
[[3],[8]]Explanation:
The tree has two types of duplicate subtrees: single node subtree [3] appears twice (as left child of root and left child of left subtree), and single node subtree [8] appears twice (as right child of root and left child of right subtree).
Input:
root = [1,2,2,3,3,3,3]Output:
[[2,3,3],[3]]Explanation:
This is a complete binary tree where the left and right subtrees rooted at value 2 are identical (both have structure [2,3,3]). Additionally, all four leaf nodes with value 3 are duplicate single-node subtrees, so returning one instance of each duplicate structure.
Constraints
- •
1 ≤ nodes ≤ 5000