共计 2873 个字符，预计需要花费 8 分钟才能阅读完成。
读完本文，你不仅学会了算法套路，还能够顺便去 LeetCode 上拿下如下题目：
652. 寻找反复的子树
———–
接前文 手把手带你刷二叉树（第一期）和 手把手带你刷二叉树（第二期），本文持续来刷二叉树。
从前两篇文章的浏览量来看，大家还是可能通过二叉树学习到 框架思维 的。但还是有不少读者有一些问题，比方 如何判断咱们应该用前序还是中序还是后序遍历的框架？
那么本文就针对这个问题，不贪多，给你掰开揉碎只讲一道题。还是那句话，依据题意，思考一个二叉树节点须要做什么，到底用什么遍历程序就分明了。
看题，这是力扣第 652 题「寻找重复子树」：
函数签名如下：
List<TreeNode> findDuplicateSubtrees(TreeNode root);我来简略解释下题目，输出是一棵二叉树的根节点 root，返回的是一个列表，外面装着若干个二叉树节点，这些节点对应的子树在原二叉树中是存在反复的。
说起来比拟绕，举例来说，比方输出如下的二叉树：
首先，节点 4 自身能够作为一棵子树，且二叉树中有多个节点 4：
相似的，还存在两棵以 2 为根的重复子树：
那么，咱们返回的 List 中就应该有两个 TreeNode，值别离为 4 和 2（具体是哪个节点都无所谓）。
这题咋做呢？还是老套路，先思考，对于某一个节点，它应该做什么。
比如说，你站在图中这个节点 2 上：
如果你想晓得以本人为根的子树是不是反复的，是否应该被退出后果列表中，你须要晓得什么信息？
你须要晓得以下两点：
1、以我为根的这棵二叉树（子树）长啥样？
2、以其余节点为根的子树都长啥样？
这就叫知己知彼嘛，我得晓得本人长啥样，还得晓得他人长啥样，而后能力晓得有没有人跟我反复，对不对？
好，那咱们一个一个来看，先来思考，我如何能力晓得以本人为根的二叉树长啥样？
其实看到这个问题，就能够判断本题要应用「后序遍历」框架来解决：
void traverse(TreeNode root) {traverse(root.left);
traverse(root.right);
/* 解法代码的地位 */
}为什么？很简略呀，我要晓得以本人为根的子树长啥样，是不是得先晓得我的左右子树长啥样，再加上本人，就形成了整棵子树的样子？
如果你还绕不过去，我再来举个非常简单的例子：计算一棵二叉树有多少个节点。这个代码应该会写吧：
int count(TreeNode root) {if (root == null) {return 0;}
// 先算出左右子树有多少节点
int left = count(root.left);
int right = count(root.right);
/* 后序遍历代码地位 */
// 加上本人，就是整棵二叉树的节点数
int res = left + right + 1;
return res;
}这不就是规范的后序遍历框架嘛，和咱们本题在实质上没啥区别对吧。
当初，明确了要用后序遍历，那应该怎么形容一棵二叉树的模样呢？咱们前文 序列化和反序列化二叉树 其实写过了，二叉树的前序 / 中序 / 后序遍历后果能够形容二叉树的构造。
所以，咱们能够通过拼接字符串的形式把二叉树序列化，看下代码：
String traverse(TreeNode root) {
// 对于空节点，能够用一个特殊字符示意
if (root == null) {return "#";}
// 将左右子树序列化成字符串
String left = traverse(root.left);
String right = traverse(root.right);
/* 后序遍历代码地位 */
// 左右子树加上本人，就是以本人为根的二叉树序列化后果
String subTree = left + "," + right + "," + root.val;
return subTree;
}咱们用非数字的非凡符 # 示意空指针，并且用字符 , 分隔每个二叉树节点值，这属于序列化二叉树的套路了，不多说。
留神咱们 subTree 是依照左子树、右子树、根节点这样的程序拼接字符串，也就是后序遍历程序。你齐全能够依照前序或者中序的程序拼接字符串，因为这里只是为了形容一棵二叉树的样子，什么程序不重要。
这样，咱们第一个问题就解决了，对于每个节点，递归函数中的 subTree 变量就能够形容以该节点为根的二叉树。
当初咱们解决第二个问题，我晓得了本人长啥样，怎么晓得他人长啥样？这样我能力晓得有没有其余子树跟我反复对吧。
这很简略呀，咱们借助一个内部数据结构，让每个节点把本人子树的序列化后果存进去，这样，对于每个节点，不就能够晓得有没有其余节点的子树和本人反复了么？
初步思路能够应用 HashSet 记录子树，代码如下：
// 记录所有子树
HashSet<String> memo = new HashSet<>();
// 记录反复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();
String traverse(TreeNode root) {if (root == null) {return "#";}
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left + "," + right+ "," + root.val;
if (memo.contains(subTree)) {
// 有人和我反复，把本人退出后果列表
res.add(root);
} else {
// 临时没人跟我反复，把本人退出汇合
memo.add(subTree);
}
return subTree;
}然而呢，这有个问题，如果呈现多棵反复的子树，后果集 res 中必然呈现反复，而题目要求不心愿呈现反复。
为了解决这个问题，能够把 HashSet 升级成 HashMap，额定记录每棵子树的呈现次数：
// 记录所有子树以及呈现的次数
HashMap<String, Integer> memo = new HashMap<>();
// 记录反复的子树根节点
LinkedList<TreeNode> res = new LinkedList<>();
/* 主函数 */
List<TreeNode> findDuplicateSubtrees(TreeNode root) {traverse(root);
return res;
}
/* 辅助函数 */
String traverse(TreeNode root) {if (root == null) {return "#";}
String left = traverse(root.left);
String right = traverse(root.right);
String subTree = left + "," + right+ "," + root.val;
int freq = memo.getOrDefault(subTree, 0);
// 多次重复也只会被退出后果集一次
if (freq == 1) {res.add(root);
}
// 给子树对应的呈现次数加一
memo.put(subTree, freq + 1);
return subTree;
}这样，这道题就齐全解决了，题目自身算不上难，然而思路拆解下来还是挺有启发性的吧？
