Sponsored
Sponsored
Utilize 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.
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.
1using System;
2using System.Collections.Generic;
3
4public class TreeNode {
5 public int val;
6 public TreeNode left;
7 public TreeNode right;
8 public TreeNode(int x) { val = x; }
9}
10
11public class Solution {
12 public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
13 var map = new Dictionary<string, List<TreeNode>>();
14 Serialize(root, map);
15 var result = new List<TreeNode>();
16 foreach (var pair in map) {
17 if (pair.Value.Count > 1) {
18 result.Add(pair.Value[0]);
19 }
20 }
21 return result;
22 }
23
24 private string Serialize(TreeNode node, Dictionary<string, List<TreeNode>> map) {
25 if (node == null) {
26 return "#";
27 }
28 string serial = node.val + "," + Serialize(node.left, map) + "," + Serialize(node.right, map);
29 if (!map.ContainsKey(serial)) {
30 map[serial] = new List<TreeNode>();
31 }
32 map[serial].Add(node);
33 return serial;
34 }
35}This C# implementation performs a tree serialization similarly to prior examples, storing serialized representations in a dictionary. Duplicate subtrees are identified through dictionary entries with multiple nodes.
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.
Time Complexity: O(N), as we traverse each node.
Space Complexity: O(N), necessary for dictionaries and recursive processing space.
1class TreeNode:
2
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.