Daily LeetCode – day0038 0652. Find Duplicate Subtrees

// 0652. Find Duplicate Subtrees
class Solution {
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        HashMap<String, ArrayList<TreeNode>> hashMap = new HashMap<>();
        Queue<TreeNode> q = new LinkedList<>();
        if (root.left != null) q.add(root.left);
        if (root.right != null) q.add(root.right);
        boolean hasNext = true;
        while (hasNext) {
            hasNext = false;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode front = q.poll();
                String s = binaryTree2String(front);
                if (hashMap.containsKey(s)) {
                    hashMap.get(s).add(front);
                } else {
                    ArrayList<TreeNode> treeNodeArrayList = new ArrayList<>();
                    treeNodeArrayList.add(front);
                    hashMap.put(s, treeNodeArrayList);
                }
                if (front.left != null) {
                    q.offer(front.left);
                    hasNext = true;
                }
                if (front.right != null) {
                    q.offer(front.right);
                    hasNext = true;
                }
            }
        }
        List<TreeNode> ans = new ArrayList<>();
        for (Map.Entry<String, ArrayList<TreeNode>> e : hashMap.entrySet()) {
            if (e.getValue().size() > 1) {
                ans.add(e.getValue().get(0));
            }
        }
        return ans;
    }

    private String binaryTree2String(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(node);
        boolean hasNext = true;
        while (hasNext) {
            hasNext = false;
            int size = q.size();
            for (int i = 0; i < size; ++i) {
                TreeNode front = q.poll();
                if (front == null) {
                    sb.append('n');
                } else {
                    sb.append('e');
                    sb.append(front.val);
                    if (front.left == null) {
                        sb.append('l');
                    } else {
                        q.offer(front.left);
                        hasNext = true;
                    }
                    if (front.right == null) {
                        sb.append('r');
                    } else {
                        q.offer(front.right);
                        hasNext = true;
                    }
                }
            }
        }
        return sb.toString();
    }
}

学习笔记：
这是一道有难度的二叉树题目，用到了二叉树的序列化。
我用的是宽度优先搜索来遍历结点，用宽度优先搜索来序列化。
其实效率上和深度优先搜索查的不多的。但是问题就在于还有更巧妙的方法。
不过想想也是，一个大子树如果有相同的，那么它下面的小子树肯定也有一堆相同了。
但是要怎么样不暴力的把他们都列出来，这就是很巧妙的问题了。
今天心浮气躁，不想做更深入的研究，就没继续做了。