NeetCode #436LC-652MediumTrees
← Back to All Problems#436 · #652 · Find Duplicate Subtrees(寻找重复的子树)
📌 Problem Statement & Constraints
Given the root of a binary tree, return all duplicate subtrees: subtrees that occur more than once anywhere in the tree, with the same structure and values. Return the root of one representative per duplicate group. Constraints: the number of nodes is in
[2, 5000], -200 <= Node.val <= 200.💡 Core Algorithmic Approaches
- Serialise each subtree into a canonical string, then count how many times each string occurs.
- A post-order DFS builds the key as
value,left_key,right_key;Nonebecomes a fixed marker. - The first time a key reaches a count of 2, record the node as a representative.
- The counting approach ensures each duplicate group is reported exactly once.
💻 Benchmark Python3 Implementation
class Solution:
def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[TreeNode]:
from collections import defaultdict
cnt = defaultdict(int)
res = []
def dfs(node: Optional[TreeNode]) -> str:
if not node:
return "#" # null marker
key = f"{node.val},{dfs(node.left)},{dfs(node.right)}"
cnt[key] += 1
if cnt[key] == 2: # record exactly once per group
res.append(node)
return key
dfs(root)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2) worst case, because the serialised keys can be O(n) long each. Using interning (assigning each unique key an integer id) makes it O(n).
💾 Space Complexity
O(n^2) for the stored keys in the worst case, or O(n) with interning.
⚠️ Interview Pitfalls & Follow-ups
- Appending on every occurrence after the first: the same subtree would be reported many times; the
== 2check is what deduplicates. - Omitting the null markers: different structures could produce the same serialisation.
- Using a pre-order key: any consistent order works as long as it is applied uniformly; post-order is conventional.
- Comparing subtrees structurally for every pair: O(n^3).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.