/*
Runtime: 360 ms, faster than 92.42% of C# online submissions for Find Duplicate Subtrees.
Memory Usage: 52.5 MB, less than 100.00% of C# online submissions for Find Duplicate Subtrees.
*/
public class Solution {
    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        var map = new Dictionary<TreeNode, string>();

        if (root != null) {
            serialize(root, map);
        }

        return map.GroupBy(kv => kv.Value).Where(g => g.Count() > 1).Select(g => g.First().Key).ToList();
    }

    private string serialize(TreeNode root, IDictionary<TreeNode, string> map) {
        var sb = new StringBuilder();
        sb.Append(root.val);

        if (root.left != null) {
            sb.Append('L');
            sb.Append(serialize(root.left, map));
        }

        if (root.right != null) {
            sb.Append('R');
            sb.Append(serialize(root.right, map));
        }

        sb.Append('.');

        var result = sb.ToString();
        map[root] = result;
        return result;
    }
}