leetcode-652 寻找重复的子树

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

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

代码实现

递归实现

class Solution {
    private HashMap<String, Integer> subTrees = new HashMap<String, Integer>();

    private List<TreeNode> duplicate = new ArrayList<TreeNode>();

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

    public String postorder(TreeNode root) {
        if (root == null) {
            return "#";
        }
        String left = postorder(root.left);
        String right = postorder(root.right);
        String subTree = left + "," + right + "," + root.val;
        int frequency = subTrees.getOrDefault(subTree, 0);
        if (frequency == 1) {
            duplicate.add(root);
        }
        subTrees.put(subTree, frequency + 1);
        return subTree;
    }
}