652. 寻找重复的子树.md

652. 寻找重复的子树

题目传送门

点击这里

解题思路

这道题的方法和序列化的思路差不多，都是用hash记录重复过的子树，然后再用一个数字记录已经遍历过一次的，那第二次就可以添加到hash中。

代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    // 使用序列化进行唯一标识，相同的子树同一个序列化，不同的子树不同的序列化
    hash := map[*TreeNode]struct{}{}
    visit := map[string]*TreeNode{}
    // 递归向下
    var dfs func(*TreeNode) string
    dfs = func(node *TreeNode) string {
        if node == nil {
            return ""
        }
        s := fmt.Sprintf("%d(%s)(%s)", node.Val, dfs(node.Left), dfs(node.Right))
        if n, ok := visit[s]; ok {
            // 第二次遍赋值空结构体给hash
            hash[n] = struct{}{}
        }else {
            // 第一次遍历在visit中记录
            visit[s] = node
        }
        return s
    }
    dfs(root)
    res := make([]*TreeNode, 0, len(hash))
    for v := range hash {
        res = append(res, v)
    }
    return res
}