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:
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]]
Constraints:
[1, 5000]-200 <= Node.val <= 200Utilize a Depth-First Search (DFS) strategy and serialize each subtree. Treat the serialization as a key in a hashmap to track occurrences of identical subtrees. Duplicate entries are detected when a serialized key is encountered more than once.
This Python solution uses DFS to serialize each subtree into a string. These strings are stored in a dictionary. If a string appears more than once, it indicates a duplicate subtree. The function returns one node from each set of duplicates.
Java
C
C++
C#
JavaScript
Time Complexity: O(N), where N is the number of nodes since we visit each node once.
Space Complexity: O(N), accounting for the hashmap to store serialized trees and recursion stack space.
Rather than using direct serialization strings, assign each unique subtree encountered a unique ID using a hash map. If a subtree's ID is seen again, it's a duplicate.
This Python approach maps each subtree structure to a unique identifier, incrementally assigning IDs using a dictionary. Duplicates are recognized when the same ID appears multiple times.
Java
C++
JavaScript
Time Complexity: O(N), as we traverse each node.
Space Complexity: O(N), necessary for dictionaries and recursive processing space.
| Approach | Complexity |
|---|---|
| Tree Serialization Using DFS | Time Complexity: O(N), where N is the number of nodes since we visit each node once. |
| Tree Serialization with Unique Identifiers | Time Complexity: O(N), as we traverse each node. |
Find Duplicate Subtrees - Leetcode 652 - Python • NeetCodeIO • 22,954 views views
Watch 9 more video solutions →Practice Find Duplicate Subtrees with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor