题目

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

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

示例 1：

下面是两个重复的子树：

      2
     /
    4

和

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

方案一（后续遍历+子树序列化）

/**
 * 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 := getPostOrder(root, m)
    return res
}

func getPostOrder(node *TreeNode, m map[string]int) (string, []*TreeNode) { // 后序遍历
    if node == nil {
        return "null", []*TreeNode{} // 不能返回 ""
    }
    left, left_res := getPostOrder(node.Left, m)
    right, right_res := getPostOrder(node.Right, m)
    res1 := left + right + strconv.Itoa(node.Val)
    // 遍历到根节点, 此时使用子树的序列化表示做为键
    res2 := []*TreeNode{}
    res2 = append(res2, left_res...)
    res2 = append(res2, right_res...)
    if val, ok := m[res1]; ok && val == 1 {
        res2 = append(res2, node)
    }
    m[res1] += 1
    return res1, res2
}

子树序列化之后作为 map 的 key 即可。

leetcode 方案，逻辑差不多，但是使用了较美观的代码。

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func findDuplicateSubtrees(root *TreeNode) []*TreeNode {
    if root == nil {
        return []*TreeNode{}
    }

    res := []*TreeNode{}
    m := map[string]int{}
    helper(root, m, &res)

    return res
}

func helper(node *TreeNode, m map[string]int, res *[]*TreeNode) string { // 前序遍历
    if node == nil {
        return "#"
    }

    s := "*" + strconv.Itoa(node.Val) + helper(node.Left, m, res) + helper(node.Right, m, res)

    if count, ok := m[s]; ok && count == 1 {
        *res = append(*res, node)
    } 
    m[s] += 1

    return s
}

原文

https://leetcode-cn.com/explore/learn/card/hash-table/206/practical-application-design-the-key/823/

算法（leetcode）

寻找重复的子树

题目

方案一（后续遍历+子树序列化）

原文