652. Find Duplicate Subtrees

Posted on Edited on In

652. Find Duplicate Subtrees

Description

Difficulty: Medium

Related Topics: Hash Table, Tree, Depth-First Search, Binary Tree

Given the root of 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 the same node values.

Example 1:

1
2
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

Example 2:

1
2
Input: root = [2,1,1]
Output: [[1]]

Example 3:

1
2
Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]

Constraints:

  • The number of the nodes in the tree will be in the range [1, 5000]
  • -200 <= Node.val <= 200

Hints/Notes

  • Serialize the (sub)tree to check if there’s duplicate
  • Use map the avoid the duplicate in return, only push to res when freq[seri] == 1

Solution

Language: C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> res;
    map<string, int> freq;

    vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
        serialize(root);
        return res;
    }

    string serialize(TreeNode* root) {
        if (root == nullptr) {
            return "#";
        }
        string seri = serialize(root->left)
              + ',' + serialize(root->right)
              + "," + to_string(root->val);

        if (freq[seri] == 1) {
            res.push_back(root);
        }
        freq[seri]++;

        return seri;
    }
};