leetcode652-寻找重复的子树

原题

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

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

示例1:

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

下面是两个重复的子树:

  2  
 /    
4  

4

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

解法

思想

将子树按照某种算法遍历序列化成字符串,作为哈希表的键。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<String,Integer> map;
    List<TreeNode> list;
    public String LRD(TreeNode node){
        StringBuilder sb = new StringBuilder();
        dfs(sb,node);
        return sb.toString();
    }
    public void dfs(StringBuilder str,TreeNode node){
        if(node == null){
            str.append('n');
            return;
        }
        dfs(str,node.left);
        dfs(str,node.right);
        str.append(String.valueOf(node.val));
        return;
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        map = new HashMap<>();
        list = new ArrayList<>();
        dfsFindSubtrees(root);
        return list;
    }
    public void dfsFindSubtrees(TreeNode root){
        if(root == null) return;
        dfsFindSubtrees(root.left);
        dfsFindSubtrees(root.right);
        String LRD = LRD(root);
        if(map.containsKey(LRD)){
            if(map.get(LRD)==1){
                list.add(root);
                map.put(LRD,0);
            }
        }else{
            map.put(LRD,1);
        }
    }
} 

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode652-%e5%af%bb%e6%89%be%e9%87%8d%e5%a4%8d%e7%9a%84%e5%ad%90%e6%a0%91/

发表回复

登录后才能评论