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.
1function TreeNode(val)
This JavaScript approach assigns unique identifiers for each different subtree structure encountered. Duplicate IDs signal subtrees that share the same structure and value arrangements.