652. 寻找重复的子树

题目

给定一棵二叉树 root，返回所有重复的子树。

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

如果两棵树具有相同的结构和相同的结点值，则它们是重复的。

示例 1：

输入：root = [1,2,3,4,null,2,4,null,null,4]
输出：[[2,4],[4]]

示例 2：

输入：root = [2,1,1]
输出：[[1]]

示例 3：

输入：root = [2,2,2,3,null,3,null]
输出：[[2,3],[3]]

提示：

• 树中的结点数在[1,10⁴]范围内。
• -200 <= Node.val <= 200

题解

如果你想知道以自己为根的子树是不是重复的，是否应该被加入结果列表中，你需要知道什么信息？
你需要知道一下两点：

1. 以我为根的这棵树二叉树（子树）长啥样？
2. 以其他节点为根的子树都长啥样？

我怎么知道以我为根的子树长啥样？可以使用二叉树的前序/中序/后序遍历描述二叉树的结构。
我怎么知道其他子树长啥样？每个节点都把以自己为根的子树的样子存到一个外部变量的数据结构中即可。

代码实现

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

var treeMap map[string]int
var nodeRes []*TreeNode

func find(root *TreeNode) []*TreeNode {
	if root == nil {
		return nil
	}
	var postorder func(node *TreeNode) string
	postorder = func(node *TreeNode) string {
		if node == nil {
			return "#"
		}
		left := postorder(node.Left)
		right := postorder(node.Right)
		subTree := fmt.Sprintf("%s,%s,%s", left, right, fmt.Sprintf("%d", node.Val))
		if cnt, ok := treeMap[subTree]; ok && cnt == 1 {
			nodeRes = append(nodeRes, node)
		}
		treeMap[subTree]++
		return subTree
	}
	postorder(root)
	return nodeRes
}