0652. Find Duplicate Subtrees

题目信息

题号:

0652

难度:

Medium

主题:

二叉树、子树结构、节点值、重复类型去重

原题:

LeetCode 0652

重点:

重复子树必须结构和值都相同、同一种重复子树只返回一个代表根节点、结果顺序不限

题目重述

给定二叉树根节点 root,找出树中所有重复子树。两棵子树只有在对应结构完全相同且每个对应节点值都相等时,才视为相同。

对于每一种至少出现两次的子树类型,返回其中任意一个实例的根节点;即使同一类型出现三次或更多次,也只在结果中放一个代表。结果顺序不限。树中节点数位于 [1, 5000],节点值位于 [-200, 200]。

自建示例

同时存在两种重复子树:

输入:root = [1,2,2,3,null,3]
输出:代表子树 [3] 和 [2,3] 的两个根节点
解释:值为 3 的叶子子树出现两次;两棵以 2 为根、左孩子为 3 的子树也完全相同,每种只返回一个代表。

节点值相同但结构不同:

输入:root = [4,2,2,1,null,null,1]
输出:[[1]]
解释:两个叶节点 1 构成重复子树;两个值为 2 的节点分别只有左孩子和右孩子,结构不同,不能归为同一种子树。