algorithm - 如何找到最大公共(public)子树

Question

有一棵树，树定义为

public class TreeNode 
{
    int val;      
    vector<TreeNode *> children;      
    TreeNode(int x) { val = x; }      
} 

求最大公共(public)子树(节点数最多，每个节点的值无所谓，只要子树的结构相同即可)

例如，

           1                   
      /    |      \                  
     2     3       4                 
    /    / | \   / | \                
   5    6  7  8  9 10 11               

根为3和4的子树是最大公共(public)子树(注意，可能有两个以上的子树是公共(public)子树)，

输出最大子树的根。

我觉得蛮力法不好，散列呢，但是我不知道怎么散列一棵树的结构。

Answer 1

哈希听起来不错。让我们切换到一般树的二叉树表示，其中二叉树的左 child 是一般树的第一个 child ，二叉树的右 child 是一般树的下一个兄弟。你的树现在看起来像这样。

      1
     / \
    2   3
   /   / \
  /   /   \
 /   /     \
5   6       4
     \     /
      7   9
       \   \
        8   10
             \
              11

我们可以使用 nil 和 cons 对这棵树进行 Lisp 风格的编码。

cons(cons(cons(nil, nil),
          nil),
     cons(cons(nil,
               cons(nil,
                    cons(nil, nil))),
          cons(cons(nil,
                    cons(nil,
                         cons(nil, nil))),
               nil)))

设H 为散列值集。如果我们在哈希值上指定一个哈希值 nil : H 和二元运算符 cons : H * H -> H，那么我们将得到一个哈希函数。这是一种可能性。设 f 为 pseudorandom function从任意长度的字符串到固定长度的哈希字符串。

nil = f("")
cons(a, b) = f(a + b)