任意两棵树的最大公共子结构

daisy8867

ufoahw 发表于 7-30-2015 04:41 AM
6 M# y! A& U/ q...，pair计算有问题，换成序列化之后的字符串再找子串，不是子序列。

! v0 I1 g! _# W  `2 b+ z; `' c* F不太理解，序列化指什么，能举个例子吗？

ufoahw

daisy8867 发表于 7-31-2015 09:24 AM
9 \! @: l6 V! e1 E8 C; q7 @不太理解，序列化指什么，能举个例子吗？

树的序列化～

uuuouou

感觉可以用分治法来解决，复杂度最坏是O(M*N*min(M, N))的：
* O( J4 S) V: n) i2 J6 X6 e, F1 T/ m

1. struct Node{
   0 w& o# [# Z9 }, _2 Q" ^9 T$ f
2.         int   val;
   0 C  d% h* z7 `+ E
3.         Node* left;
   
4.         Node* right;
   # G9 b3 v% L3 {4 c
5.         Node(int v): val(v), left(nullptr), right(nullptr){}
   & g; z; G, c; L/ S
6. };
   
7. 
   . w3 @" E% Z& L  [
8. vector<const Node*> getCommonPart(const Node* p, const Node* q)//以p和q为树根向下找相同结构，并以先序的存储顺序返回相同部分在树p中对应的节点指针
   
9. {
   
10.         if(!p || !q || p->val != q->val) return vector<const Node*>();
    
11. 
    
12.         vector<const Node*> cp;
    
13.         cp.push_back(p);
    0 d" z2 o7 F8 x! I6 F5 P- Q8 N
14. 
    2 D1 }+ B! C3 {* m) l4 |1 w
15.         auto lp = getCommonPart(p->left, q->left);
    
16.         auto rp = getCommonPart(p->right, q->right);
    ! M, w: p! n/ h5 L2 G- q
17. 
    . ?$ f" }7 ]5 X6 K8 c1 A8 ^! S5 I
18.         cp.insert(cp.end(), lp.begin(), lp.end());
    
19.         cp.insert(cp.end(), rp.begin(), rp.end());
    
20. 
    
21.         return cp;
    / ?$ u" x, Z& {7 @, x& b; [! k4 t' A6 w
22. }
    5 l8 v$ N) @' C' S) j. J" C
23. 
      B4 [3 \, Y5 _  [$ K1 e' P
24. vector<const Node*> getLargestCommonPart(const Node* p, const Node* q)//找出树p和树q的最大相同部分，返回相同部分在树p中对应的节点指针
    
25. {
    8 k. r4 |% B& o; H" M1 D  j
26.     if(!p || !q) return vector<const Node*>();
    " |- Q3 A: q" Q) n9 d! m
27. 
    ( |# l/ D# \8 @* `0 G' n
28.     vector<const Node*> lcp, *pLargest = &lcp;
    
29.     if(p->val == q->val){
    
30.         lcp = getCommonPart(p, q);
    
31.     }
    ! t9 x0 L! a* H8 f: b1 [/ I) K
32.     // divide and conquer
    
33.     auto p_left_lcp = getLargestCommonPart(p->left, q);
    
34.     auto p_right_lcp = getLargestCommonPart(p->right, q);
    
35.     auto q_left_lcp = getLargestCommonPart(p, q->left);
    
36.     auto q_right_lcp = getLargestCommonPart(p, q->right);
    3 y; {& }. l1 }' ?; f
37. 
    
38.     // choose one with the largest size
    2 }0 q) D( c  I/ B9 R
39.     if(pLargest->size() < p_left_lcp.size())  pLargest = &p_left_lcp;
    
40.     if(pLargest->size() < p_right_lcp.size()) pLargest = &p_right_lcp;
    
41.     if(pLargest->size() < q_left_lcp.size())  pLargest = &q_left_lcp;
    , e+ @: y! l3 B( t7 I
42.     if(pLargest->size() < q_right_lcp.size()) pLargest = &q_right_lcp;
    / W+ a* e% D, b; e* D) A
43. 
    
44.     return *pLargest;
    . f2 \  k& s: M
45. }
    

复制代码

+ ], P  ^( b, {, T5 v( x( X上面代码得到的是最大相同结构的节点集合，如果想要恢复出这个相同的结构（做一个deep copy），则可以用树遍历的方式来做

1. void cloneCommonPart(Node* pNew, const Node* pOld, unordered_set<const Node*>& commonSet)
   
2. {
   
3.         if(commonSet.count(pOld->left)){
   - B  n6 \8 |; X$ m
4.                 pNew->left = new Node(pOld->left->val);
   
5.                 cloneCommonPart(pNew->left, pOld->left, commonSet);
   1 i% i$ J$ B- d: V/ x2 O# a
6.         }
   
7.         if(commonSet.count(pOld->right)){
   
8.                 pNew->right = new Node(pOld->right->val);
   - g' \! g! J, h) K( ~, P2 `
9.                 cloneCommonPart(pNew->right, pOld->right, commonSet);
   
10.         }
    : k/ R" t5 w  d+ X
11. }
    
12. Node* cloneCommonPart(const vector<const Node*>& cp)//相同的部分可能是任意形式的树，clone出这一相同的部分
    " `) W6 b( }, A9 I9 J
13. {
    
14.         if(cp.empty()) return nullptr;
    
15. 
    5 w+ l  d8 j/ Q4 i7 X  G" u
16.         const Node* pOld = cp[0];
    
17.         Node* pNew = new Node(pOld->val);
    
18.         unordered_set<const Node*> commonSet(cp.begin(), cp.end());
    
19. 
    
20.         cloneCommonPart(pNew, pOld, commonSet);
    5 `. n$ J7 M8 ]8 F5 V) C
21.         return pNew;
    $ }' S$ `3 q" `9 u7 X
22. }

复制代码