寻找重复的子树

题目描述

给定一棵二叉树的根节点 root，请找出所有重复的子树。

如果两棵子树具有相同的结构，并且对应位置上的节点值也完全相同，则认为它们是重复的。

对于每一类重复子树，只需要输出其中任意一棵的根节点对应的整棵子树即可。

为保证输出唯一，本题规定：

• 当某种子树第一次被判定为“重复”时，记录当前这棵子树；
• 最终按照记录顺序输出这些重复子树；
• 每棵子树使用其层序序列表示，并去掉末尾多余的 null。

输入格式

第一行输入一个整数 n，表示二叉树层序序列的长度。

第二行输入 n 个字符串，表示二叉树的层序遍历结果，其中：

• 非 null 字符串表示该节点的整数值；
• null 表示该位置为空节点。

保证输入序列能够唯一确定一棵二叉树，且根节点非空。

输出格式

第一行输出一个整数 k，表示重复子树的种类数。

接下来输出 k 行。每行先输出一个整数 m，表示该子树层序序列长度；随后输出 m 个字符串，表示该子树的层序序列。

数据范围

1 <= n <= 5000

-200 <= Node.val <= 200

样例 1

输入

9
1 2 3 4 null 2 4 null null 4

输出

2
2 4
3 2 4