<p>Given the <code>root</code>&nbsp;of a binary tree, return all <strong>duplicate subtrees</strong>.</p>

<p>For each kind of duplicate subtrees, you only need to return the root node of any <b>one</b> of them.</p>

<p>Two trees are <strong>duplicate</strong> if they have the <strong>same structure</strong> with the <strong>same node values</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/16/e1.jpg" style="width: 450px; height: 354px;" />
<pre>
<strong>Input:</strong> root = [1,2,3,4,null,2,4,null,null,4]
<strong>Output:</strong> [[2,4],[4]]
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/16/e2.jpg" style="width: 321px; height: 201px;" />
<pre>
<strong>Input:</strong> root = [2,1,1]
<strong>Output:</strong> [[1]]
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/08/16/e33.jpg" style="width: 450px; height: 303px;" />
<pre>
<strong>Input:</strong> root = [2,2,2,3,null,3,null]
<strong>Output:</strong> [[2,3],[3]]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li>The number of the nodes in the tree will be in the range <code>[1, 5000]</code></li>
	<li><code>-200 &lt;= Node.val &lt;= 200</code></li>
</ul>

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from itertools import combinations

class UnionFind:

    def __init__(self, n):
        self.tree = list(range(n))
        self.rank = [0]*n
    
    def find(self, i):
        if self.tree[i] != i:
            self.tree[i] = self.find(self.tree[i])
        return self.tree[i]
    
    def connected(self, i, j):
        return self.find(i) == self.find(j)

    def union(self, i, j):
        if self.connected(i, j):
            return

        i, j = self.find(i), self.find(j)
        
        if self.rank[i] <= self.rank[j]:
            self.tree[i] = j
            self.rank[j] += self.rank[i]
        else:
            self.tree[j] = i
            self.rank[i] += self.rank[j]

    def components(self):
        sizes = Counter()
        for j in range(len(self.tree)):
            i = self.find(j)
            sizes[i] += 1

        return [i for i in sizes if sizes[i] > 1]

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        nodes = []
        Q = deque([root])
        while Q:
            node = Q.pop()
            nodes.append(node)
            for child in [node.left, node.right]:
                if child:
                    Q.appendleft(child)
        
        subtree_sizes = {}
        indices = {}
        subtrees_by_size = []
        for node in reversed(nodes):
            subtree_sizes[node] = 1
            for child in [node.left, node.right]:
                if child:
                    subtree_sizes[node] += subtree_sizes[child]
            size = subtree_sizes[node]
            while len(subtrees_by_size) < size:
                subtrees_by_size.append([])
            subtrees_by_size[size - 1].append(node)
            indices[node] = len(subtrees_by_size[size - 1]) - 1
        
        duplicates = []
        UFs = []

        for size, roots in enumerate(subtrees_by_size):
            num_roots = len(roots)
            UFs.append(UnionFind(num_roots))
            UF = UFs[-1]
            for i, j in combinations(range(num_roots), 2):
                root1, root2 = roots[i], roots[j]
                if root1.val != root2.val:
                    continue
                if root1.left and not root2.left:
                    continue
                if root2.right and not root2.right:
                    continue
                if root2.left and not root1.left:
                    continue
                if root2.right and not root1.right:
                    continue
                if root1.left and subtree_sizes[root1.left] != subtree_sizes[root2.left]:
                    continue
                if root1.right and subtree_sizes[root1.right] != subtree_sizes[root2.right]:
                    continue
                same = True
                if root1.left:
                    size_left = subtree_sizes[root1.left]
                    i1, j1 = indices[root1.left], indices[root2.left]
                    same &= UFs[size_left - 1].connected(i1, j1)
                if root1.right:
                    size_right = subtree_sizes[root1.right]
                    i1, j1 = indices[root1.right], indices[root2.right]
                    same &= UFs[size_right - 1].connected(i1, j1)
                if same:
                    UF.union(i, j)
            duplicates.extend([roots[i] for i in UF.components()])
        
        return duplicates
18001