关于java:二叉树题型框架3

老话放在后面依据题意，思考一个二叉树节点须要做什么，到底用什么遍历程序就分明了
寻找反复的子树

对于某个节点，如何晓得本人是不是反复的
1.以我为根的这棵二叉树(子树)长啥样？
2.以其余节点为根的子树都长啥样？
咱们如何晓得本人长啥样呢，能够用后序遍历的框架来解决
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;}

咱们用非数字的非凡符#示意空指针，并且用字符，分隔每个二叉树节点值，这属于序列化二叉树的套路。
对于每个节点来说，递归函数中的subTree变量就能够形容以该节点为根的二叉树
接下来，如何晓得他人长什么样？
咱们能够创立一个内部变量，通过将序列化后的后果保留在其中，那么咱们就能够晓得他人是不是曾经有过了，如果曾经存在的话，东哥的代码也解释了一开始应用的是Set构造，那么做完比照的后果就有多个反复的res,所以应用HashMap。

HashMap<String,Integer> memo=new HashMap<>();LinkedList<TreeNode> res=new LinkedList<>();List<TreeNode> findDuplicationSubtrees(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=meomo.getOrDefault(subTree,0);if(freq==1){res.add(root);}memo.put(subTree,freq+1);return subTree;}