中等

问题描述

给定一棵二叉树 root，返回所有重复的子树。

对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

示例 2：

输入：root = [2,1,1]
输出：[[1]]

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

• 树中的结点数在 [1,104]范围内。
• -200 <= Node.val <= 200

DFS+序列化+哈希表

以树的各个节点作为根节点对树进行序列化操作，同时记录序列化后的结果，若序列化过程中出现相同的序列，说明以当前节点为根节点的树是存在重复的，将它加入到结果中。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode[]}
 */
var findDuplicateSubtrees = function (root) {
  const map = new Map()
  const ans = []
  const serialize = (node) => {
    if (!node) return '#'
    let s = node.val
    s += ',' + serialize(node.left)
    s += ',' + serialize(node.right)
    if (map.get(s) === 1) {
      ans.push(node)
    }
    map.set(s, (map.get(s) || 0) + 1)
    return s
  }
  serialize(root)
  return ans
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$