652_find_duplicate_subtrees

652. 寻找重复的子树 中等

给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。

两棵树重复是指它们具有相同的结构以及相同的结点值。

示例 1：

        1
       / \
      2   3
     /   / \
    4   2   4
       /
      4

下面是两个重复的子树：

      2
     /
    4

和

    4

因此，你需要以列表的形式返回上述重复子树的根结点。

代码参考：

package main

import (
    "fmt"
    "strconv"
)

func main() {
    tree := &TreeNode{Val: 1}
    tree.Left = &TreeNode{Val: 2}
    tree.Left.Left = &TreeNode{Val: 4}
    tree.Right = &TreeNode{Val: 3}
    tree.Right.Left = &TreeNode{Val: 2}
    tree.Right.Left.Left = &TreeNode{Val: 4}
    tree.Right.Right = &TreeNode{Val: 4}

    for _, node := range findDuplicateSubtrees(tree) {
        fmt.Println(node.Val) // ok
    }
}

func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    paths := make(map[string]int)
    var res []*TreeNode
    traverse(root, paths, &res)
    return res
}

// 后序遍历把路径放到 map 中去重
func traverse(root *TreeNode, paths map[string]int, res *[]*TreeNode, ) string {
    if root == nil {
        return "#"
    }

    fullPath := strconv.Itoa(root.Val) + "," + traverse(root.Left, paths, res) + "," + traverse(root.Right, paths, res)
    if count, ok := paths[fullPath]; ok && count == 1 { // 计数 count 为 1
        *res = append(*res, root)
    }
    paths[fullPath]++

    return fullPath
}