/*
Runtime: 676 ms, faster than 14.39% of C# online submissions for Find Duplicate Subtrees.
Memory Usage: 128.3 MB, less than 100.00% of C# online submissions for Find Duplicate Subtrees.
*/
public class Solution {
    private const string NullRepresentation = "[[null]]";

    public IList<TreeNode> FindDuplicateSubtrees(TreeNode root) {
        var map = new Dictionary<TreeNode, string>();

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

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

    private void dfs(TreeNode root, IDictionary<TreeNode, string> map) {
        var sb = new StringBuilder();
        sb.AppendFormat("{0:x8}", root.val);

        if (root.left != null) {
            dfs(root.left, map);
            sb.Append(map[root.left]);
        }
        else {
            sb.Append(NullRepresentation);
        }

        if (root.right != null) {
            dfs(root.right, map);
            sb.Append(map[root.right]);
        }
        else {
            sb.Append(NullRepresentation);
        }

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