思路

问题一：如果遍历比较

• 遍历所有节点，然后两两比较。时间复杂度O(n)。一看性能就不行。
• 利用set来判断是否重复。不过有重复多次的情况，但只需返回一个重复节点，所以还需要记录count，使用map即可。

问题二：如何判断两个节点结构相同

• 通过递归，同时遍历两个节点。因为一个节点需要和多次比较，所以同一个节点需要遍历多次，性能差。
• 序列化二叉树。将二叉树遍历，转成字符串。不过需要注意
  1. 中序无法反序列化
  2. 中序的序列化是不能确定二叉树的，前序和后序就行。具体原因还没想清楚，正在LeetCode请教大佬。
     
     

题目

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

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

示例 1：

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

下面是两个重复的子树：

      2
     /
    4

和

    4

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

代码

class Solution {
        private List<TreeNode> res = new ArrayList<>();
        private Map<String, Integer> memo = new HashMap<>();

        public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
            serializeNode(root);
            return res;
        }

        private String serializeNode(TreeNode root) {
            if (root == null) {
                return "#";
            }

            String left = serializeNode(root.left);
            String right = serializeNode(root.right);
            // 序列化二叉树
            String curr = left + "," + right + "," + root.val;

            Integer count = memo.getOrDefault(curr, 0);
            if (count == 1) {
                res.add(root);
            }
            memo.put(curr, count + 1);
            return curr;
        }
    }