# C#, group nodes by max depth, LINQ with custom tree IEqualityComparer to sort out duplicates; no hashes or serialization

• Duplicate trees must have same height. So the idea is to traverse the tree once, group nodes in a dictionary based on height. Then look for duplicates in each group.

Uses a simple TreeEqualityComparer : IEqualityComparer<TreeNode> comparer class for finding duplicates.

I could also make postorder tree traversal non-recursive, but it got accepted just like this (uses recursion). Enjoy.

public class Solution
{
IDictionary<int,List<TreeNode>> layers = new Dictionary<int, List<TreeNode>>();

TreeEqualityComparer tcomparer = new TreeEqualityComparer();

public IList<TreeNode> FindDuplicateSubtrees(TreeNode root)
{
dfs(root);

var list = new List<TreeNode>();

foreach (var layer in layers.Keys)  if (layers[layer].Count > 1)
{
list.AddRange( layers[layer].GroupBy(t => t, tcomparer).Where(g => g.Count() > 1).Select(g => g.Key) );
}

return list;
}

int dfs(TreeNode root)
{
if (root == null)  return 0;

int layer = Math.Max( root.left  != null  ?  dfs(root.left)  : 0,
root.right != null  ?  dfs(root.right) : 0 ) + 1;

return layer;
}

{

}

class TreeEqualityComparer : IEqualityComparer<TreeNode>
{
public bool Equals(TreeNode t1, TreeNode t2)
{
return  (t1 != null && t2 != null)  ?
(t1.val == t2.val) && Equals(t1.left, t2.left)  && Equals(t1.right, t2.right)  :
!(t1 == null ^ t2 == null);
}

public int GetHashCode(TreeNode root)
{
return (root == null) ? 0 : root.val;
}
}
}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.