Как найти максимальное общее поддерево

Question

есть дерево, а дерево определяются как

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

пожалуйста найти maxmum общего поддерево (имеет наибольшее количество узлов, то вал каждый узла не имеет значения , только структура поддеревьев быть тем же самым)

ех,

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

поддерева с корнем 3 и 4 являются maxmum общим поддерево (обратите внимание, что может быть больше, чем два поддерева являются общим поддерево) ,

выводятся корни максимальных поддерев.

Я думаю, что метод грубой силы не очень хорош, а как насчет хэширования, но я не понимаю, как хешировать структуру дерева .

Answer 1

Хешинг звучит хорошо. Перейдем к представлению двоичного дерева общих деревьев, где левым дочерним элементом двоичного дерева является первый дочерний элемент общего дерева, а правый дочерний элемент двоичного дерева - следующий брат общего дерева. Теперь ваше дерево выглядит так.

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

Мы можем закодировать это дерево Lisp-стиль, используя nil и cons.

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)