java - 如何在多树中找到最大的公共(public)子树

Question

最近遇到一道算法题:树定义为

public class Node 
{
    int id;      
    private final List<Node> children;
    Node(int id) {
        this.id = id;
        this.children = new ArrayList<>();
    }      
} 

Two subtrees are in common if their structure is identical. The largest common subtrees maximizes the number of nodes in each individual subtrees. So how to find the maxmum common subtree(the id of each node does not matter, just the structure of the subtrees be the same). If there are separate groups of subtrees that are in common with the same maximal size, then we should should return the root nodes from all of the subtrees.

我的想法是使用 BFS 将每个子树序列化为唯一的字符串。我们得到所有的字符串后，对它们进行排序，比较哪两个相等。所以下面是我的代码。我的问题是因为每个子树的序列化会导致很多开销，是否有任何其他想法可以更好的时间复杂度来解决这个问题。

public static List<Node> getLargestCommonSubtrees(Node root) {
        HashMap<String, ArrayList<Node>> map = new HashMap<String, ArrayList<Node>>();
        LinkedList<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.pollFirst();
            String sig = serialize(cur);
            if (map.containsKey(sig)) {
                ArrayList<Node> list = map.get(sig);
                list.add(cur);
                map.put(sig, list);
            } else {
                ArrayList<Node> list = new ArrayList<Node>();
                list.add(cur);
                map.put(sig, list);
            }
            for (int i = 0; i < cur.children.size(); i++) {
                if (cur.children.get(i) != null) {
                    queue.add(cur.children.get(i));
                }
            }
        }
        int max = Integer.MIN_VALUE;
        ArrayList<Node> ans = new ArrayList<Node>();
        for (Entry<String, ArrayList<Node>> e : map.entrySet()) {
            if (e.getKey().length() >= max) {
                if (e.getKey().length() > max) {
                    ans.clear();
                }
                ans.addAll(e.getValue());
            }
        }
        return ans;
    }

private static String serialize(Node n) {
        String signature = "";
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(n);
        if (n.children.size() == 0) {
            signature = "0";
            return signature;
        }
        Node curr = null;
        while (!q.isEmpty()) {
            curr = q.peek();
            q.poll();
            signature += String.valueOf(curr.children.size());
            for (int i = 0; i < curr.children.size(); i++) {
                q.offer(curr.children.get(i));
            }
        }
        return signature;
    }

Answer 1

JoJo，对于这个或类似的问题，可能已经存在有效的算法。但是，这是我的做法。

import java.util.ArrayList;
import java.util.List;


public class Node
{
    //signature = number of Node's children + signature of each child     =  total number of all nodes below this Node (including children and children's children...etc)
    //
    // for example, a tree would have it's signature as
    //             13
    //      1       5        4  
    //      0    1    2    1   1
    //           0   0 0   0   0
    //
    private int signature;

    private int id;      
    private final List<Node> children;
    private Node parent;

    public Node(int id, Node parent) {
        this.id = id;
        this.children = new ArrayList<Node>();
        this.parent = parent;
    }

    //updates signature, should be called every time there is a change to Node.
    private void updateSignature() {
        signature = children.size();

        for(Node childNode : children) {
            signature += childNode.signature;
        }

        //tell parent to update it's signature
        if(parent != null) {
            parent.updateSignature();
        }
    }

    //compares two trees to check if their structure is similar
    private boolean hasSameStructureAs(Node otherNode) {
        return otherNode != null && signature == otherNode.signature;
    }
}