Spot the twin subtrees
Find the subtrees that appear more than once in a tree, by giving each distinct subtree an id built from its children's ids and counting how often each id appears. About 20 minutes.
An id for every shape
Two subtrees are twins if they have the same shape and the same values. To find twins quickly, give each distinct subtree a number, its id, so that twins get the same id. An empty subtree gets id 0.
A subtree is fully described by three things: the id of its left subtree, its own value, and the id of its right subtree. If two subtrees have the same three, they are twins.
ids = {}
key = (1, 5, 2)
if key not in ids:
ids[key] = len(ids)- repeated
- leaf 7
The leaves 7 and 7 have the same description: an empty left, the value 7, an empty right. They share an id, and it appears twice.
Count the ids
You need the children's ids before you can describe a node, so work bottom-up: finish both children first, then the node. This is a postorder walk.
Keep a counter of how many times each id appears. At the end, the number of ids with a count of two or more is the number of distinct subtrees that occur more than once. A pair of twins is counted once, not per node.
counts[i] = counts.get(i, 0) + 1
repeated = [i for i in counts
if counts[i] > 1]A leaf 4 appears three times in a tree. How much does it add to the count of repeated subtrees?
- A1, since it is one distinct subtree that repeats
- B3
- C2, the number of extra copies
Show the answer
1, since it is one distinct subtree that repeats. The count is of distinct repeated shapes, not of nodes.
Count the repeated subtrees
Given the root of a binary tree, return the number of distinct subtrees that appear more than once. Two subtrees are the same if they have the same structure and the same node values. A leaf counts as a subtree. A shape that occurs three or more times is still counted once.
root = [1, 2, 3, 4, null, 2, 4, null, null, 4] → 2
0 ≤ number of nodes ≤ 5,000 · -200 ≤ node.val ≤ 200