⚡Flashcard Drill➔
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

  1. Serialise each subtree into a canonical string, then count how many times each string occurs.
  2. A post-order DFS builds the key as value,left_key,right_key; None becomes a fixed marker.
  3. The first time a key reaches a count of 2, record the node as a representative.
  4. 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 == 2 check 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems