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


  • 0
    C

    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;
            
            add(root, layer);
            
            return layer;
        }
        
        void add(TreeNode node, int layer)
        {
            if (!layers.ContainsKey(layer)) layers.Add(layer, new List<TreeNode>());
    
            layers[layer].Add(node);
        }
        
        
        
        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;
            }
        }
    }
    

Log in to reply
 

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