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

有一棵树，树的定义是

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

请找到最大公共子树（节点数最多，每个节点的值无关紧要，只是子树的结构相同）
前任，

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

根为3和4的子树是最大公共子树（注意，可能有两个以上的子树是公共子树）。
输出最大子树的根。
我觉得蛮力法不好，散列怎么办，但我不知道怎么散列
树的结构。

最佳答案

散列听起来不错。让我们切换到一般树的二叉树表示，其中二叉树的左子是一般树的第一个子，而二叉树的右子是一般树的下一个同级。你的树现在看起来是这样的。

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

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

关于algorithm - 如何找到最大的公共(public)子树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/25726676/