652. 寻找重复的子树
题目描述
输入一棵二叉树的根节点 root，用层序数组表示，null 表示空位。
以某个节点为根、连同其全部后代构成一棵子树。如果两棵子树形状相同，并且对应位置的节点值也都相同，就认为它们重复。
找出所有至少出现两次的子树。同一类重复子树只需返回其中任意一棵的根节点，结果列表的顺序不限。输出中每棵子树都以它自己的层序数组表示。
示例 1
输入：root = [1,2,3,4,null,2,4,null,null,4] 输出：[[4],[2,4]]
解释：子树 [4] 出现了三次，子树 [2,4] 出现了两次。
示例 2
输入：root = [2,1,1] 输出：[[1]]
解释：两个叶子 1 构成的子树相同。
示例 3
输入：root = [2,2,2,3,null,3,null] 输出：[[3],[2,3]]
解释：子树 [3] 和 [2,3] 各出现两次。
数据范围
- 节点数在
[1, 5000]范围内。 -200 <= Node.val <= 200
解题思路：子树序列化 + 哈希表
把每棵子树序列化成一个唯一的字符串：后序遍历，先拿到左右子树的字符串，再拼成“值,左,右”，空节点用 # 表示。结构和值都相同 ⇔ 字符串相同。用哈希表记录每个字符串出现的次数，恰好第 2 次出现时把当前节点加入答案，这样每类只加一次。
为什么正确
ser(node) 返回的字符串唯一确定以 node 为根的子树；处理完 node 时，它的全部后代都已计入哈希表。
复杂度分析
时间 O(n²)：每个节点拼接的字符串长度可达 O(n)（用整数编号代替字符串可优化到 O(n)）；空间 O(n²)。
易错点
序列化必须包含空节点标记和分隔符：只拼值会把 [1,2] 与 [1,null,2]、或 "1"+"12" 与 "11"+"2" 混淆。另外要用“次数恰好等于 2”而不是“大于等于 2”，否则同一类会被加入多次。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
seen = {}
ans = []
def ser(node):
if not node:
return '#'
key = str(node.val) + ',' + ser(node.left) + ',' + ser(node.right)
seen[key] = seen.get(key, 0) + 1
if seen[key] == 2:
ans.append(node)
return '(' + key + ')'
ser(root)
return ansclass Solution {
Map<String, Integer> seen = new HashMap<>();
List<TreeNode> ans = new ArrayList<>();
String ser(TreeNode node) {
if (node == null)
return "#";
String key = node.val + "," + ser(node.left) + "," + ser(node.right);
seen.merge(key, 1, Integer::sum);
if (seen.get(key) == 2)
ans.add(node);
return "(" + key + ")";
}
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
ser(root);
return ans;
}
}class Solution {
unordered_map<string, int> seen;
vector<TreeNode*> ans;
string ser(TreeNode* node) {
if (!node)
return "#";
string key = to_string(node->val) + "," + ser(node->left) + "," + ser(node->right);
seen[key]++;
if (seen[key] == 2)
ans.push_back(node);
return "(" + key + ")";
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
ser(root);
return ans;
}
};func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
seen := map[string]int{}
ans := []*TreeNode{}
var ser func(node *TreeNode) string
ser = func(node *TreeNode) string {
if node == nil {
return "#"
}
key := strconv.Itoa(node.Val) + "," + ser(node.Left) + "," + ser(node.Right)
seen[key]++
if seen[key] == 2 {
ans = append(ans, node)
}
return "(" + key + ")"
}
ser(root)
return ans
}var findDuplicateSubtrees = function(root) {
const seen = new Map();
const ans = [];
const ser = (node) => {
if (!node)
return '#';
const key = node.val + ',' + ser(node.left) + ',' + ser(node.right);
seen.set(key, (seen.get(key) || 0) + 1);
if (seen.get(key) === 2)
ans.push(node);
return '(' + key + ')';
};
ser(root);
return ans;
};function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
const seen = new Map<string, number>();
const ans: TreeNode[] = [];
const ser = (node: TreeNode | null): string => {
if (!node)
return '#';
const key = node.val + ',' + ser(node.left) + ',' + ser(node.right);
seen.set(key, (seen.get(key) || 0) + 1);
if (seen.get(key) === 2)
ans.push(node);
return '(' + key + ')';
};
ser(root);
return ans;
}其他解法
两种解法都用后序遍历给子树生成唯一标识；序列化字符串长度随子树增长，最坏 O(n²)，三元组编号把标识压缩成整数，降到 O(n)。
解法 2：三元组编号 时间 O(n)，空间 O(n)
给每种不同的子树结构分配一个整数编号，空树编号为 0。后序遍历时，先得到左右子树的编号，再用三元组 (val, 左编号, 右编号) 在哈希表中查找。三元组已存在就复用其编号，否则分配新编号。某个编号第二次出现时，把当前节点加入答案。
每个节点的键长度是常数，避免了序列化字符串随子树增长。代价是需要理解“子树相同当且仅当三元组相同”这一归纳关系。
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
ids = {}
count = {}
ans = []
def dfs(node):
if not node:
return 0
key = (node.val, dfs(node.left), dfs(node.right))
if key not in ids:
ids[key] = len(ids) + 1
uid = ids[key]
count[uid] = count.get(uid, 0) + 1
if count[uid] == 2:
ans.append(node)
return uid
dfs(root)
return ansclass Solution {
Map<String, Integer> ids = new HashMap<>();
Map<Integer, Integer> cnt = new HashMap<>();
List<TreeNode> ans = new ArrayList<>();
int dfs(TreeNode node) {
if (node == null) return 0;
String key = node.val + "," + dfs(node.left) + "," + dfs(node.right);
Integer uid = ids.get(key);
if (uid == null) {
uid = ids.size() + 1;
ids.put(key, uid);
}
int c = cnt.merge(uid, 1, Integer::sum);
if (c == 2) ans.add(node);
return uid;
}
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
dfs(root);
return ans;
}
}class Solution {
map<tuple<int, int, int>, int> ids;
unordered_map<int, int> cnt;
vector<TreeNode*> ans;
int dfs(TreeNode* node) {
if (!node) return 0;
int l = dfs(node->left);
int r = dfs(node->right);
auto key = make_tuple(node->val, l, r);
auto it = ids.find(key);
int uid;
if (it == ids.end()) {
uid = ids.size() + 1;
ids[key] = uid;
} else {
uid = it->second;
}
if (++cnt[uid] == 2) ans.push_back(node);
return uid;
}
public:
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
dfs(root);
return ans;
}
};func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
ids := map[[3]int]int{}
cnt := map[int]int{}
ans := []*TreeNode{}
var dfs func(node *TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return 0
}
key := [3]int{node.Val, dfs(node.Left), dfs(node.Right)}
uid, ok := ids[key]
if !ok {
uid = len(ids) + 1
ids[key] = uid
}
cnt[uid]++
if cnt[uid] == 2 {
ans = append(ans, node)
}
return uid
}
dfs(root)
return ans
}var findDuplicateSubtrees = function(root) {
const ids = new Map();
const cnt = new Map();
const ans = [];
const dfs = (node) => {
if (!node) return 0;
const key = node.val + ',' + dfs(node.left) + ',' + dfs(node.right);
let uid = ids.get(key);
if (uid === undefined) {
uid = ids.size + 1;
ids.set(key, uid);
}
const c = (cnt.get(uid) || 0) + 1;
cnt.set(uid, c);
if (c === 2) ans.push(node);
return uid;
};
dfs(root);
return ans;
};function findDuplicateSubtrees(root: TreeNode | null): Array<TreeNode | null> {
const ids = new Map<string, number>();
const cnt = new Map<number, number>();
const ans: TreeNode[] = [];
const dfs = (node: TreeNode | null): number => {
if (!node) return 0;
const key = node.val + ',' + dfs(node.left) + ',' + dfs(node.right);
let uid = ids.get(key);
if (uid === undefined) {
uid = ids.size + 1;
ids.set(key, uid);
}
const c = (cnt.get(uid) || 0) + 1;
cnt.set(uid, c);
if (c === 2) ans.push(node);
return uid;
};
dfs(root);
return ans;
}