LeetCode-652. 寻找重复的子树

题目描述：

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

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

示例 1：

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

下面是两个重复的子树：

      2
     /
    4

和

    4

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

思路分析;

• 首先解决如何寻找重复的问题，要找重复的子树，如果重复了就保存一个树的根节点。这已经提示我们，遍历整棵树的所有节点，遍历的时候我们想办法得到以这个结点为根的子树的情况是什么样子的，显然用序列化二叉树，如何记录重复？这里我想到用哈希如果对应子树的序列出现次数超过1次那么就重复了，需要在结果中加入该子树的根结点。
• 再就是如何遍历树？我们知道树分三种遍历方式：前序，中序和后序，这三种都是深度优先搜索DFS。当然还有层次遍历，不过这个属于广度优先搜索BFS理论上讲这4种遍历方式都是可行的，因为按照我们对问题的分析，我们仅仅只需要遍历整棵树的结点，但从遍历来讲，这几种方法都是可以达到目的的。
• 如何序列化二叉树？我们知道要想序列和二叉树一一对应，只有前序序列和后序序列才可以。按照序列化的模板就OK啦，返回一个string类型的字符串，各个结点用逗号隔开，空指针用#表示。

代码实现：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     

          HashMap<String,Integer> memo=new HashMap<>();
     
    
   

    

     

    
    

     

          LinkedList<TreeNode> res=new LinkedList<>();
     
    
   

    

     

    
    

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

    

     

    
    

     

          }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：小小谢先生，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/xiewenrui1996/article/details/113980098