Comment on page

652.Find-Duplicate-Subtrees

652. Find Duplicate Subtrees

题目地址

题目描述

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.
​
Two trees are duplicate if they have the same structure with same node values.
​
Example 1:
​
1
/ \
2 3
/ / \
4 2 4
/
4
The following are two duplicate subtrees:
​
2
/
4
and
​
4
Therefore, you need to return above trees' root in the form of a list.

代码

Approach #1 DFS

Time: O(N^2) where N is the number of nodes in the tree. We visit each node once, but each creation of serial may take O(N) work.
Space: O(N^2) the size of count
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
Map<String, Integer> count = new HashMap();
List<TreeNode> ans = new ArrayList();
collect(root, count, ans);
return ans;
}
​
private String collect(TreeNode node, Map<String, Integer> count, List<TreeNode> ans) {
if (node == null) return "#";
​
String serial = node.val + "," + collect(node.left, count, ans) + "," + collect(node.right, count, ans);
count.put(serial, count.getOrDefault(serial, 0) + 1);
if (count.get(serial) == 2) {
ans.add(node);
}
return serial;
}
}

Approach #2 Unique Identifier

Time: O(N log N)
Space: O(N)
class Solution {
int t;
Map<String, Integer> trees;
Map<Integer, Integer> count;
List<TreeNode> ans;
​
public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
t = 1;
trees = new HashMap();
count = new HashMap();
ans = new ArrayList();
lookup(root);
return ans;
}
​
private int loopup(TreeNode node) {
if (node == null) return 0;
String serial = node.val + "," + lookup(node.left) + "," + lookup(node.right);
int uid = trees.computeIfAbsent(serial, x -> t++);
if (count.get(uid) == 2) {
ans.add(nodes);
}
return uid;
}
​
}