LeetCode 652: Find Duplicate Subtrees

Question

I'm posting my code for a LeetCode problem copied here. If you have time and would like to review, please do so. Thank you!

Problem

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.

Code

#include <vector>
#include <unordered_map>
#include <string>
class Solution {
public:
 std::vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
 std::unordered_map<string, std::vector<TreeNode *>> nodes_map;
 std::vector<TreeNode *> duplicates;
 this->serialize(root, nodes_map);
 for (auto iter = nodes_map.begin(); iter != nodes_map.end(); iter++) {
 if (iter->second.size() > 1) {
 duplicates.push_back(iter->second[0]);
 }
 }
 return duplicates;
 }
private:
 std::string serialize(TreeNode *node, std::unordered_map<std::string, std::vector<TreeNode *>> &nodes_map) {
 if (!node) {
 return "";
 }
 std::string serialized = "[" + serialize(node->left, nodes_map) + std::to_string(node->val) + serialize(node->right, nodes_map) + "]";
 nodes_map[serialized].push_back(node);
 return serialized;
 }
};

Reference

LeetCode has a template for answering questions. There is usually a class named Solution with one or more public functions which we are not allowed to rename. For this question, the template is:

/**
 * 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*> findDuplicateSubtrees(TreeNode* root) {
 
 }
};

• Problem

• Solution

• Discuss

• Tree Data Structure

Answer 1

You forgot a std::

There's a string without std:: in front of it. I guess you secretly used using namespace std and/or #include <bits/stdc++.h> before submitting the result. The rest looks fine though.

Consider using const TreeNode * everywhere

I know the public API of the LeetCode problem explicitly takes non-const pointers to TreeNode, so you shouldn't change this. But consider that your functions, quite rightly so, don't modify the TreeNodes themselves. So you could write const TreeNode * everywhere you now have TreeNode *, and it would still compile correctly. So in real production code, that is what you should do.

Don't use this-> unnecessarily

In C++, there is rarely a need to write this->. So in findDuplicateSubtrees(), you can just write serialize(root, nodes_map).

Use range-for and structured bindings where appropriate

You can replace the for-loop in findDuplicateSubtrees() using range-for and structured bindings:

for (auto &[serialization, nodes]: nodes_map) {
 if (nodes.size() > 1) {
 duplicates.push_back(nodes[0]);
 }
}

Consider using a binary serialization format

There are many ways you could serialize trees. Making human-readable strings has some advantages: it is easy to reason about, and it is nice when having to put them in textual formats like XML or JSON files. But it can be inefficient to convert values to strings. In your case, you are only using the serialization internally, so a binary format might be more efficient.

In the case of trees of integers, an obvious representation is just a vector of ints. However, a node might have only one child, and you somehow have to encode that as well. You could use a std::optional<int>, and use std::nullopt to represent an unpopulated leaf node. The serialization format would then be:

std::vector<std::optional<int>> serialization;

The serialization function would then look like:

std::vector<std::optional<int>> serialize(TreeNode *node, std::unordered_map<std::string, std::vector<TreeNode *>> &nodes_map) {
 if (!node) {
 return {std::nullopt};
 }
 auto left = serialize(node->left, nodes_map);
 auto right = serialize(nodes->right, nodes_map);
 left.append(node->val);
 left.insert(left.end(), right.begin(), right.end()); // append right
 return left;
}

For the LeetCode problem, it's not worth doing this though; the algorithmic complexity is the same, and the string representation is smaller for trees with small values. Also, you can not use a std::unordered_map anymore for nodes_map, unless you write a custom hash function. You could use a std::map though, since optionals and vectors have well-defined ordering.