Find duplicate subtrees

Hash Table Tree Depth-First Search Binary Tree

60.6% acceptance

Feb 20, 2026

6115

503

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;
impl Solution {
  pub fn find_duplicate_subtrees(
    root: Option<Rc<RefCell<TreeNode>>>,
  ) -> Vec<Option<Rc<RefCell<TreeNode>>>> {
    let mut map: HashMap<String, i32> = HashMap::new();
    let mut result = Vec::new();
    fn serialize(
      node: &Option<Rc<RefCell<TreeNode>>>,
      map: &mut HashMap<String, i32>,
      result: &mut Vec<Option<Rc<RefCell<TreeNode>>>>,
    ) -> String {
      match node {
        None => "#".to_string(),
        Some(n) => {
          let b = n.borrow();
          let left = serialize(&b.left, map, result);
          let right = serialize(&b.right, map, result);
          let key = format!("{},{},{}", b.val, left, right);
          let count = map.entry(key.clone()).or_insert(0);
          *count += 1;
          if *count == 2 {
            result.push(Some(Rc::clone(n)));
          }
          key
        }
      }
    }
    serialize(&root, &mut map, &mut result);
    result
  }
}