LeetCode: Find Duplicate Subtrees

// https://code.dennyzhang.com/find-duplicate-subtrees
// Basic Ideas: hashmap
// Encode binarytree to string
// Complexity: Time O(n), Space O(n)
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    m := map[string]int{}
    res := []*TreeNode{}
    postTree(root, m, &res)
    return res
}

func postTree(root *TreeNode, m map[string]int, res *[]*TreeNode) string {
    if root == nil { return "#" }
    l, r := postTree(root.Left, m, res), postTree(root.Right, m, res)
    v := fmt.Sprintf("%s,%s,%d", l, r, root.Val)
    if m[v] == 1 { *res = append(*res, root) }
    m[v]++
    return v
}