444. Find Duplicate Subtrees
You are given the root of a binary tree. Call two subtrees duplicates when they have exactly the same shape and exactly the same values in every position. (A subtree consists of some node together with all of its descendants.)
Your function receives the root node and returns a list of TreeNode references: one representative root for each distinct subtree that occurs two or more times anywhere in the tree.
Return the representatives in any order — the grader canonicalizes the output by serializing each reported subtree in preorder (with null markers for missing children) and sorting those serializations as strings. If the tree has no duplicate subtrees, return an empty list.
Example 1:
Input: root = [1, 2, 3, 4, null, 2, 4, null, null, 4]
Output: [[2, 4], [4]]
Explanation: The leaf 4 appears three times, and the subtree 2-with-left-child-4 appears twice (under the root and under node 3). One representative of each is reported.
Example 2:
Input: root = [2, 1, 1]
Output: [[1]]
Explanation: Both children of the root are the identical leaf 1, so that leaf subtree is the only duplicate.
Constraints:
- 1 ≤ number of nodes ≤ 2000
- -200 ≤ Node.val ≤ 200
Hints:
Comparing every pair of subtrees node by node works but repeats an enormous amount of work. Can you give every subtree a fingerprint, so that two subtrees are identical exactly when their fingerprints are equal?
Build the fingerprint bottom-up in one postorder pass: a node's encoding combines its value with its children's encodings (include a marker for missing children, or shapes become ambiguous). Count encodings in a hash map and record a node the moment its encoding's count reaches exactly 2 — that yields one representative per duplicate. Mapping each (value, leftId, rightId) triple to a small integer id keeps every step O(1).
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [1, 2, 3, 4, null, 2, 4, null, null, 4]
Expected output: [[2, 4], [4]]