leetcode-go/leetcode/medium/652.find-duplicate-subtrees.go

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findDuplicateSubtrees(root *TreeNode) (res []*TreeNode) {
	m := make(map[string]int)
	helper(root, m, &res)
	return res
}

func helper(root *TreeNode, m map[string]int, res *[]*TreeNode) string {
	if root == nil {
		return "#"
	}
	path := helper(root.Left, m, res) + " " + helper(root.Right, m, res) + " " + strconv.Itoa(root.Val)
	if m[path] == 1 {
		*res = append(*res, root)
	}
	m[path]++
	return path
}