Find Duplicate Subtrees

https://leetcode.com/problems/find-duplicate-subtrees/description/

Given a binary tree, return all duplicate subtrees. For each kind of duplicate subtrees, you only need to return the root node of any one of them.

Two trees are duplicate if they have the same structure with same node values.

Thoughts

先尝试分治，并不行，因为左右子树重复的树可能并不在它们各自返回的结果里，还是需要重新访问左右子树查抄有没有相同的。后来看到别人的解法，和Serialize思路类似，把每个子树转成string, 只是这里要把每个substring都记录下来。看到有些人在争论是先序还是后序。虽然写法看上去是先序，但由于是左右子树先返回然后再加的当前结点，所以实际上是后序。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private String postOrder(TreeNode node, Map<String, Integer> strings, List<TreeNode> res) {
        if (node == null) {
            return "#";
        }
        String str = node.val + "," + postOrder(node.left, strings, res) + "," + postOrder(node.right, strings, res);
        if (strings.getOrDefault(str, 0) == 1) {
            res.add(node);
        }
        strings.put(str, strings.getOrDefault(str, 0) + 1);;
        return str;
    }

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        postOrder(root, new HashMap<>(), res);
        return res;
    }
}

Analysis

时间复杂度为一次后续遍历，O(n)。

Ver.2

同样原理iterative实现. 需要把每个节点对应的string存下来, 因此需要额外的map.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private final String NULL = "#";
    private final String SPLITER = "/";

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        List<TreeNode> res = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        Map<String, Integer> freqs = new HashMap<>();
        Map<TreeNode, String> map = new HashMap<>();
        map.put(null, NULL + SPLITER);
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root, pre = null;
        while (cur != null || !stack.isEmpty()) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }

            TreeNode node = stack.peek();
            if (!map.containsKey(node)) {
                map.put(node, node.val + SPLITER);
            }
            map.put(node, map.get(node) + map.get(pre));

            if (node.right != null && node.right != pre) {
                pre = null;
                cur = node.right;
                continue;
            }
            String sub = map.get(node);
            if (node.right == null) {
                map.put(node, sub + NULL + SPLITER);
            }
            //System.out.println(map.get(node));
            pre = stack.pop();
            freqs.put(map.get(node), freqs.getOrDefault(map.get(node), 0) + 1);
            if (freqs.get(map.get(node)) == 2) {
                res.add(node);
            }
        }

        return res;
    }
}