leetcode刷题（98）——652. 寻找重复的子树

本文主要是介绍leetcode刷题（98）——652. 寻找重复的子树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

示例 1：

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

下面是两个重复的子树：

2/4

和

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

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 记录所有子树以及出现的次数HashMap<String, Integer> memo = new HashMap<>();ArrayList<TreeNode> result = new ArrayList();public List<TreeNode> findDuplicateSubtrees(TreeNode root) {help(root);return result;}String help(TreeNode root){if(root == null){return "#";}String left = help(root.left);String right = help(root.right);String tree = left+","+right+","+root.val;int freq = memo.getOrDefault(tree, 0);// 多次重复也只会被加入结果集一次if (freq == 1) {result.add(root);}// 给子树对应的出现次数加一memo.put(tree, freq + 1);return tree;}
}

其实看到这个问题，就可以判断本题要使用「后序遍历」框架来解决：

void traverse(TreeNode root) {traverse(root.left);traverse(root.right);/* 解法代码的位置 */
}

我要知道以自己为根的子树长啥样，是不是得先知道我的左右子树长啥样，再加上自己，就构成了整棵子树的样子？
我们可以通过拼接字符串的方式把二叉树序列化，看下代码：

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;
}

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {// 记录所有子树以及出现的次数HashMap<String, Integer> memo = new HashMap<>();ArrayList<TreeNode> result = new ArrayList();public List<TreeNode> findDuplicateSubtrees(TreeNode root) {help(root);return result;}String help(TreeNode root){if(root == null){return "#";}String left = help(root.left);String right = help(root.right);String tree = left+","+right+","+root.val;int freq = memo.getOrDefault(tree, 0);// 多次重复也只会被加入结果集一次if (freq == 1) {result.add(root);}// 给子树对应的出现次数加一memo.put(tree, freq + 1);return tree;}
}