找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

楼主: daisy8867
收起左侧

[面经题目讨论] 任意两棵树的最大公共子结构

[复制链接]

14

主题

1

精华

321

积分

高级会员

Rank: 3Rank: 3

积分
321
 楼主| 发表于 7-31-2015 09:24 AM | 显示全部楼层
ufoahw 发表于 7-30-2015 04:41 AM
6 M# y! A& U/ q...,pair计算有问题,换成序列化之后的字符串再找子串,不是子序列。

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

10

主题

4

精华

251

积分

高级会员

Rank: 3Rank: 3

积分
251
发表于 8-1-2015 03:41 PM | 显示全部楼层
daisy8867 发表于 7-31-2015 09:24 AM
9 \! @: l6 V! e1 E8 C; q7 @不太理解,序列化指什么,能举个例子吗?
% P4 m+ G2 S0 Z+ l
树的序列化~

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-5-2015 11:02 AM | 显示全部楼层
感觉可以用分治法来解决,复杂度最坏是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;0 j! \1 F' b/ N- Q
  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. };. C: Q. M$ m: D

  7. . w3 @" E% Z& L  [
  8. vector<const Node*> getCommonPart(const Node* p, const Node* q)//以p和q为树根向下找相同结构,并以先序的存储顺序返回相同部分在树p中对应的节点指针- Y, t2 D0 U. m; x& |) b
  9. {. P: {: C% v2 C( ]5 c
  10.         if(!p || !q || p->val != q->val) return vector<const Node*>();8 r' B" G, E1 t! Z
  11. # ]: Q2 J0 K: D# Y, L5 P' x
  12.         vector<const Node*> cp;1 h1 i+ j# @* X: B- e9 h
  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);8 R- R7 W3 S' X) O) D. e
  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());8 N# I9 H0 a( o
  19.         cp.insert(cp.end(), rp.begin(), rp.end());7 l% Y$ g: G5 G( U5 _
  20. : R7 l3 T' S! K! ]8 n
  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中对应的节点指针" y) X% B  E# t5 n$ L7 `# R- ^
  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;' p3 H' W% C, o7 b6 Y
  29.     if(p->val == q->val){' H' E( ?. F1 z/ F; E% ]- L! Z
  30.         lcp = getCommonPart(p, q);* \% q6 f/ G9 i0 E3 D1 f
  31.     }
    ! t9 x0 L! a* H8 f: b1 [/ I) K
  32.     // divide and conquer7 D& g- y! W3 l$ o
  33.     auto p_left_lcp = getLargestCommonPart(p->left, q);" `3 h8 F2 u: F- v
  34.     auto p_right_lcp = getLargestCommonPart(p->right, q);  U# a) J6 F. b% \& i
  35.     auto q_left_lcp = getLargestCommonPart(p, q->left);/ J2 E8 ^8 d3 {, a3 F
  36.     auto q_right_lcp = getLargestCommonPart(p, q->right);
    3 y; {& }. l1 }' ?; f
  37. 9 Y( k9 x8 I) C  y+ V3 h, s. P" l4 M
  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;$ O+ S4 T( f, B8 C3 h4 s
  40.     if(pLargest->size() < p_right_lcp.size()) pLargest = &p_right_lcp;$ N* b/ j/ {0 n1 D
  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. 3 B5 }8 s9 O+ v/ \* [
  44.     return *pLargest;
    . f2 \  k& s: M
  45. }) ]+ P! L2 ?; v" n1 q7 t
复制代码

+ ], P  ^( b, {, T5 v( x( X上面代码得到的是最大相同结构的节点集合,如果想要恢复出这个相同的结构(做一个deep copy),则可以用树遍历的方式来做0 O8 u: p% y3 l+ x' p
  1. void cloneCommonPart(Node* pNew, const Node* pOld, unordered_set<const Node*>& commonSet)( V  U; ^" P+ C# S; ^6 |
  2. {  e7 p+ R! o5 C; E# I5 N
  3.         if(commonSet.count(pOld->left)){
    - B  n6 \8 |; X$ m
  4.                 pNew->left = new Node(pOld->left->val);: t" Z. N3 L+ e; Y1 M# o3 L
  5.                 cloneCommonPart(pNew->left, pOld->left, commonSet);
    1 i% i$ J$ B- d: V/ x2 O# a
  6.         }5 S$ {" [- l( P# O- P
  7.         if(commonSet.count(pOld->right)){5 X# n. V0 G" G  d% {
  8.                 pNew->right = new Node(pOld->right->val);
    - g' \! g! J, h) K( ~, P2 `
  9.                 cloneCommonPart(pNew->right, pOld->right, commonSet);( S  x3 H( u, H" l7 M! w1 }# b" G( I
  10.         }
    : k/ R" t5 w  d+ X
  11. }2 ]- L* @# X6 ?2 W/ E6 i$ A
  12. Node* cloneCommonPart(const vector<const Node*>& cp)//相同的部分可能是任意形式的树,clone出这一相同的部分
    " `) W6 b( }, A9 I9 J
  13. {6 r/ U# z+ [% f
  14.         if(cp.empty()) return nullptr;+ v0 s6 b6 ~9 l+ Z9 k. }

  15. 5 w+ l  d8 j/ Q4 i7 X  G" u
  16.         const Node* pOld = cp[0];2 z/ m; ~7 @/ F# q, h1 f! v4 V
  17.         Node* pNew = new Node(pOld->val);( e. X- \! W; ]- b
  18.         unordered_set<const Node*> commonSet(cp.begin(), cp.end());+ i& }& x( U+ l+ Z
  19. & m, p# P1 g' c' q
  20.         cloneCommonPart(pNew, pOld, commonSet);
    5 `. n$ J7 M8 ]8 F5 V) C
  21.         return pNew;
    $ }' S$ `3 q" `9 u7 X
  22. }
复制代码
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表