grid47 Exploring patterns and algorithms
Sep 2, 2024
5 min read
Solution to LeetCode 652: Find Duplicate Subtrees Problem
Given the root of a binary tree, return all duplicate subtrees. For each duplicate subtree, return the root node of any one of them. Two trees are considered duplicates if they have the same structure and node values.
Problem
Approach
Steps
Complexity
Input: The input is the root of a binary tree, represented as an array of integers where null indicates no child for a node.
Example: root = [1,2,3,4,null,2,4,null,null,4]
Constraints:
• 1 <= number of nodes <= 5000
• -200 <= Node.val <= 200
Output: Return a list of root nodes of duplicate subtrees. Each node in the output should be the root of a duplicate subtree.
Example: [[2,4],[4]]
Constraints:
• Only return the root of any duplicate subtree.
Goal: Identify and return the root of all duplicate subtrees.
Steps:
• 1. Traverse the tree in a depth-first manner.
• 2. For each subtree, serialize its structure into a string.
• 3. Use a hash map to store the frequency of each serialized subtree.
• 4. If a subtree appears more than once, add its root node to the result.
Goal: The number of nodes in the tree will be in the range [1, 5000], and node values will be between -200 and 200.
Steps:
• 1 <= n <= 5000
• -200 <= Node.val <= 200
Assumptions:
• The input tree may contain duplicate subtrees that need to be identified.
• Input: root = [1,2,3,4,null,2,4,null,null,4]
• Explanation: In this tree, the subtree [2,4] and the subtree [4] are repeated, so they are returned as the output.
Approach: Use serialization of the subtrees to identify duplicates. Each subtree is represented as a string, and a hashmap is used to track how many times each subtree occurs.
Observations:
• We need an efficient way to compare subtrees, and serializing them into strings is a good strategy.
• Hash maps can help store the serialized subtrees and detect duplicates.
Steps:
• 1. Traverse the tree and serialize each subtree into a string representation.
• 2. Use a hashmap to store serialized strings and their corresponding subtree roots.
• 3. If a subtree appears more than once, add the root to the result list.
Empty Inputs:
• The input tree will not be empty, as it is guaranteed to have at least one node.
Large Inputs:
• For large input sizes (up to 5000 nodes), ensure that the solution is optimized for time and space.
Special Values:
• Handle cases where there are no duplicate subtrees, in which case the output should be an empty list.
Constraints:
• The tree can have up to 5000 nodes, so ensure the solution is efficient.
The `findDuplicateSubtrees` function is defined to return a vector of TreeNode pointers representing the duplicate subtrees in the given binary tree rooted at `root`.
2 : Map Initialization
unordered_map<string, vector<TreeNode*>> mp;
An unordered map `mp` is created to store serialized subtree strings as keys and the corresponding vector of TreeNode pointers as values.
3 : Subtree Serialization
serialise(mp, root);
The helper function `serialise` is called to serialize the binary tree, populating the map `mp` with serialized subtree strings and corresponding TreeNode pointers.
4 : Result Vector Initialization
vector<TreeNode*> res;
A vector `res` is initialized to store the duplicate subtrees.
5 : Map Iteration
for(autoit: mp) {
The function iterates over each entry in the map `mp`, where the key is the serialized subtree string and the value is a vector of TreeNode pointers representing that subtree.
6 : Check for Duplicates
if(it.second.size() >1)
If the vector associated with a serialized subtree string has more than one element, it means the subtree is a duplicate.
7 : Store Duplicate Subtree
res.push_back(it.second[0]);
The first occurrence of the duplicate subtree is added to the result vector `res`.
8 : Return Results
return res;
The function returns the vector `res` containing the duplicate subtrees.
The current node's value is combined with the serialized representations of its left and right subtrees, enclosed in parentheses, to form a complete string representation of the current subtree.
12 : Map Update
mp[s].push_back(root);
The serialized string `s` is used as a key in the map `mp`, and the current node is added to the vector of TreeNode pointers for that subtree.
13 : Return Serialized String
return s;
The serialized string `s` representing the current subtree is returned.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: In the worst case, we traverse the tree once, and each subtree serialization takes linear time relative to its size.
Best Case: O(n)
Worst Case: O(n)
Description: Space complexity is O(n) due to the space used by the hashmap and the recursion stack for tree traversal.
