给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值。
示例 1:
1
/ \
2 3
/ / \
4 2 4
/
4
下面是两个重复的子树:
2
/
4
和
4
/**
* @param {TreeNode} root
* @return {TreeNode[]}
*/
var findDuplicateSubtrees = function(root) {
const map = new Map();
const res = [];
traverse(root);
return res;
function traverse(node) {
if (!node) {
return '#';
}
const leftStr = traverse(node.left);
const rightStr = traverse(node.right);
// 获取自己这棵树的序列化结果
const treeStr = `${node.val}.${leftStr}.${rightStr}`;
// 将序列化结果放到map里
map.set(treeStr, (map.get(treeStr) || 0) + 1)
// 如果有2个 说明是重复的 加进结果数组
if (map.get(treeStr) === 2) {
res.push(node)
}
return treeStr;
}
};