652. Find Duplicate Subtrees
1. Description
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.
2. Example
Example 1:
Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]
Example 2:
Input: root = [2,1,1]
Output: [[1]]
Example 3:
Input: root = [2,2,2,3,null,3,null]
Output: [[2,3],[3]]
3. Constraints
- The number of the nodes in the tree will be in the range [1, 5000]
- -200 <= Node.val <= 200
4. Solutions
Hash Table
n is the number of nodes in root
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public:
vector<TreeNode *> findDuplicateSubtrees(TreeNode *root) {
traverse_(root);
return result_;
}
private:
int index_ = 1;
unordered_map<long, int> tree_index_;
vector<TreeNode *> result_;
int traverse_(TreeNode *root) {
if (root == nullptr) {
return 0;
} else {
long left_index = traverse_(root->left);
long right_index = traverse_(root->right);
// make sure all values are positive
long tree_value = (((long)root->val + 256) << 32) + (left_index << 16) + right_index;
if (tree_index_.find(tree_value) == tree_index_.end()) {
tree_index_[tree_value] = index_++;
} else {
if (tree_index_[tree_value] > 0) {
tree_index_[tree_value] *= -1;
result_.push_back(root);
}
}
return abs(tree_index_[tree_value]);
}
}
};