leetcode-javascript/solutions/0652-find-duplicate-subtrees.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Find Duplicate Subtrees
 * Time Complexity: O(N)
 * Space Complexity: O(N)
 */
var findDuplicateSubtrees = function (root) {
  const subtreeSerializationCounts = new Map();
  const foundDuplicateSubtreeRoots = [];

  function getSerialization(currentTree) {
    if (!currentTree) {
      return "#";
    }

    const leftPartSerialization = getSerialization(currentTree.left);
    const rightPartSerialization = getSerialization(currentTree.right);

    const fullTreeSerialization = `${currentTree.val},${leftPartSerialization},${rightPartSerialization}`;

    const currentSerializationCount =
      (subtreeSerializationCounts.get(fullTreeSerialization) || 0) + 1;
    subtreeSerializationCounts.set(
      fullTreeSerialization,
      currentSerializationCount,
    );

    if (currentSerializationCount === 2) {
      foundDuplicateSubtreeRoots.push(currentTree);
    }

    return fullTreeSerialization;
  }

  getSerialization(root);

  return foundDuplicateSubtreeRoots;
};