leetcode652. 寻找重复的子树

leetcode652. 寻找重复的子树

三月 22, 2020

leetcode652. 寻找重复的子树

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

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

示例 1：

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

下面是两个重复的子树：

 2
/
4

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

思路1暴力解决

我没有想到下面的序列化解法.用hashmap存储已经访问过的节点,值作为key,value是一个list,包含所有值为key的节点,然后每次遍历到相同值得节点时候去访问list,看list里面的节点有没有和当前节点的结构一样的,没有一样的就加入ans中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        traverse(root);
        return ans;
    }
    public HashMap<Integer,ArrayList>map=new HashMap<>();
    public ArrayList<TreeNode>ans=new ArrayList();
    public void traverse(TreeNode root){
        if(root==null)return;
        if(!map.containsKey(root.val)){
            ArrayList<TreeNode>list=new ArrayList<>();
            list.add(root);
            map.put(root.val,list);
        }else{
            ArrayList<TreeNode>list=map.get(root.val);
            for(TreeNode node:list){
                boolean j=judge(node,root);
                if(j){
                    boolean j2=false;
                    //防止加入结构一样的节点
                    for(TreeNode tn:ans){
                        j2=judge(tn,root);
                        if(j2==true)break;
                    }
                    if(!j2)ans.add(root);
                }
            }
            list.add(root);
        }
        traverse(root.left);
        traverse(root.right);
    }
    public boolean judge(TreeNode nodeA,TreeNode nodeB){
        if(nodeA==nodeB&&nodeA==null)return true;
        if((nodeA==null&&nodeB!=null)||(nodeA!=null&&nodeB==null))return false;
        if(nodeA.val==nodeB.val){
            boolean left=judge(nodeA.left,nodeB.left);
            boolean right=judge(nodeA.right,nodeB.right);
            return left&&right;
        }
        return false;
    }
}

解法二:序列化

把每个子树序列化变成字符串,这样就只需比较字符串是否一样就可以了.
下面还对他做了优化,map存储,key是字符串,value是他出现的次数,如果次数为2,那么就说明出现了两次,这样还能解决多次相同结构子树的判断.
并且后序遍历是自底向上的,只需要遍历n个节点. 而前序遍历和中序遍历都是自顶向下,如果这么构造序列会需要n2的复杂度.(这是新学到的)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
     public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        List<TreeNode> res = new ArrayList<TreeNode>();
        findDuplicateSubtrees(root, res, map);
        return res;
    }
    
    private StringBuilder findDuplicateSubtrees(TreeNode root, List<TreeNode> res, Map<String, Integer> map){
        if(root == null){
            return new StringBuilder("$");
        }
        StringBuilder left = findDuplicateSubtrees(root.left, res, map);
        StringBuilder right = findDuplicateSubtrees(root.right, res, map);
        //注意这里的加和顺序
        // StringBuilder treeKey = left.append(new StringBuilder(root.val + "")).append(right);
        StringBuilder treeKey = new StringBuilder(root.val + "").append(left).append(right);
        map.put(treeKey.toString(), map.getOrDefault(treeKey.toString(), 0) + 1);
        if(map.get(treeKey.toString()) == 2){
            res.add(root);
        }
        return treeKey;
    }
}

leetcode 61/100