1 #include <stdio.h> 2 #include <stdlib.h> // for calloc(), free() 3 #include <assert.h> // for assert() 4 5 /* 2013.7.12 6 * 问题：设计一个算法，找出二叉树上任意两个结点的最近共同父节点。 7 * PS. 结点中数据均不同 8 */ 9 typedef struct TreeNode TreeNode; 10 typedef struct ListNode ListNode; 11 12 struct TreeNode 13 { 14 int m_nValue; 15 TreeNode *m_pLeft; 16 TreeNode *m_pRight; 17 }; 18 19 #define DEBUG 0 20 21 struct ListNode 22 { 23 #if DEBUG 24 int m_nValue; // for test. 25 #else 26 TreeNode *m_pData; 27 #endif 28 ListNode *m_pNext; 29 }; 30 31 struct ListHead 32 { 33 ListNode *m_pStart; // 指向开始结点 34 ListNode *m_pEnd; // 指向末尾结点 35 }; 36 37 typedef struct ListHead ListHead; 38 39 // Construct lookup tree. 40 void InsertNodeToTree( TreeNode **pStart, int value ) 41 { 42 if ( NULL == *pStart ) 43 { 44 TreeNode *pCur = (TreeNode *) calloc( 1, sizeof(TreeNode) ); 45 if ( pCur == NULL ) 46 { 47 printf( "Error for calloc. " ); 48 return; 49 } 50 51 pCur->m_nValue = value; 52 pCur->m_pLeft = NULL; 53 pCur->m_pRight = NULL; 54 *pStart = pCur; 55 } 56 else 57 { 58 TreeNode *pCur = *pStart; 59 60 if ( pCur->m_nValue > value ) 61 { 62 InsertNodeToTree( &pCur->m_pLeft, value ); 63 } 64 else if ( pCur->m_nValue < value ) 65 { 66 InsertNodeToTree( &pCur->m_pRight, value ); 67 } 68 else 69 { 70 printf( "The value is in tree. " ); 71 } 72 } 73 } 74 75 // Output the tree data. 76 void InOrder( TreeNode *pStart ) 77 { 78 if ( pStart != NULL ) 79 { 80 if ( pStart->m_pLeft != NULL ) 81 { 82 InOrder( pStart->m_pLeft ); 83 } 84 85 printf( "%d, ", pStart->m_nValue ); 86 87 if ( pStart->m_pRight != NULL ) 88 { 89 InOrder( pStart->m_pRight ); 90 } 91 } 92 } 93 94 // Destroy the tree 95 void DestroyTree( TreeNode **pStart ) 96 { 97 if ( *pStart != NULL ) 98 { 99 TreeNode *pCur = *pStart; 100 if ( pCur->m_pLeft != NULL ) 101 DestroyTree( &pCur->m_pLeft ); 102 103 if ( pCur->m_pRight != NULL ) 104 DestroyTree( &pCur->m_pRight ); 105 106 free( pCur ); 107 pCur = NULL; 108 } 109 } 110 111 // 正序插入结点。 112 void CreateListHead( ListHead **pStart ) 113 { 114 ListHead *pCur = (ListHead *)calloc( 1, sizeof(ListHead) ); 115 assert( pCur != NULL ); 116 pCur->m_pEnd = NULL; 117 pCur->m_pStart = NULL; 118 *pStart = pCur; 119 } 120 121 // Destroy list 122 void DestroyList( ListHead **pStart ) 123 { 124 ListNode *pCur = (*pStart)->m_pStart; 125 ListNode *pTmp = NULL; 126 127 while ( pCur != NULL ) 128 { 129 pTmp = pCur; 130 pCur = pCur->m_pNext; 131 free( pTmp ); 132 pTmp = NULL; 133 } 134 135 free( *pStart ); 136 *pStart = NULL; 137 } 138 139 // Insert node to list. 140 #if DEBUG 141 void InsertNodeToList( ListHead *pStart, int value ) // for test 142 #else 143 void InsertNodeToList( ListHead *pStart, TreeNode *value ) 144 #endif 145 146 { 147 ListNode *pCur = (ListNode *) calloc( 1, sizeof(ListNode) ); 148 assert( pCur != NULL ); 149 #if DEBUG 150 pCur->m_nValue = value; // for test 151 #else 152 pCur->m_pData = value; 153 #endif 154 pCur->m_pNext = NULL; 155 if ( pStart->m_pStart == NULL ) 156 { 157 pStart->m_pStart = pCur; 158 pStart->m_pEnd = pCur; 159 } 160 else 161 { 162 // Insert node to end. 163 pStart->m_pEnd->m_pNext = pCur; 164 pStart->m_pEnd = pCur; 165 } 166 } 167 168 void OutputList( ListHead *pStart ) 169 { 170 ListNode *pCur = pStart->m_pStart; 171 172 while ( pCur != NULL ) 173 { 174 #if DEBUG 175 printf( "%d, ", pCur->m_nValue ); // for test 176 #else 177 printf( "%d, ", pCur->m_pData->m_nValue ); 178 #endif 179 pCur = pCur->m_pNext; 180 } 181 } 182 #if DEBUG 183 void TestTree() 184 { 185 int arry[] = { 12, 10, 11, 9, 14, 13, 15 }, 186 index = 0, 187 nlen = 0; 188 TreeNode *pRoot = NULL; 189 190 nlen = sizeof(arry) / sizeof(int); 191 for ( ; index < nlen; ++index ) 192 InsertNodeToTree( &pRoot, arry[index] ); 193 194 InOrder( pRoot ); 195 DestroyTree( &pRoot ); 196 } 197 198 199 void TestList() 200 { 201 int index = 0, nlen = 12; 202 ListHead *pStart = NULL; 203 204 CreateListHead( &pStart ); 205 for ( ; index < nlen; ++index ) 206 { 207 InsertNodeToList( pStart, index ); 208 } 209 OutputList( pStart ); 210 DestroyList( &pStart ); 211 } 212 #endif 213 214 /* 2013.7.13 215 * 解决问题部分： 216 */ 217 int IsInTree( TreeNode *pStart, int value, ListHead *pHead ) 218 { 219 if ( pStart != NULL ) 220 { 221 if ( pStart->m_nValue == value ) 222 { 223 InsertNodeToList( pHead, pStart ); 224 return 1; 225 } 226 227 if ( pStart->m_nValue > value 228 && pStart->m_pLeft != NULL 229 && IsInTree( pStart->m_pLeft, value, pHead ) == 1) 230 { 231 InsertNodeToList( pHead, pStart ); 232 return 1; 233 } 234 235 if ( pStart->m_nValue < value 236 && pStart->m_pRight != NULL 237 && IsInTree( pStart->m_pRight, value, pHead ) == 1) 238 { 239 InsertNodeToList( pHead, pStart ); 240 return 1; 241 } 242 } 243 244 return 0; 245 } 246 247 int LengthList( ListHead *pStart ) 248 { 249 int cnt = 0; 250 ListNode *pCur = pStart->m_pStart; 251 252 assert( pStart != NULL ); 253 254 for ( ; pCur != 0; ++cnt, pCur = pCur->m_pNext ); 255 256 return cnt; 257 } 258 259 // 查找两个了链表第一个交点。若没有则返回NULL。 260 TreeNode* LookForFirstIntersection( ListHead *ph1, ListHead *ph2 ) 261 { 262 ListNode *p1Cur = ph1->m_pStart, 263 *p2Cur = ph2->m_pStart; 264 int nlen1 = 0, 265 nlen2 = 0, 266 diff = 0; 267 268 assert( ph1 != NULL && ph2 != NULL ); 269 nlen1 = LengthList( ph1 ); 270 nlen2 = LengthList( ph2 ); 271 272 // 长的链表先走两个链表之差的长度。 273 if ( nlen1 > nlen2 ) 274 { 275 diff = nlen1 - nlen2; 276 for ( ; diff > 0; --diff, p1Cur = p1Cur->m_pNext ); 277 } 278 else 279 { 280 diff = nlen2 - nlen1; 281 for ( ; diff > 0; --diff, p2Cur = p2Cur->m_pNext ); 282 } 283 284 while ( p2Cur != NULL && p1Cur != NULL ) 285 { 286 if ( p1Cur->m_pData == p2Cur->m_pData ) 287 return p1Cur->m_pData; 288 p1Cur = p1Cur->m_pNext; 289 p2Cur = p2Cur->m_pNext; 290 } 291 292 return NULL; 293 } 294 295 // 共同父节点。若其中一个节点是另一个结点的子节点，则输出这个节点。 296 int RecentCommonAncestor( TreeNode *pStart, int lhs, int rhs ) 297 { 298 ListHead *plHead = NULL, 299 *prHead = NULL; 300 TreeNode *pCur = NULL; 301 302 CreateListHead( &plHead ); 303 CreateListHead( &prHead ); 304 305 if ( IsInTree( pStart, lhs, plHead ) == 1 306 && IsInTree( pStart, rhs, prHead ) == 1 ) 307 { 308 printf( " The path of lhs is " ); 309 OutputList( plHead ); 310 printf( " The path of rhs is " ); 311 OutputList( prHead ); 312 313 // lookup for the first node which two lists intersect. 314 pCur = LookForFirstIntersection( plHead, prHead ); 315 } 316 317 DestroyList( &plHead ); 318 DestroyList( &prHead ); 319 320 if ( pCur != NULL ) 321 return pCur->m_nValue; 322 else 323 return 0; 324 } 325 326 void TestRCA() 327 { 328 int arry[] = { 12, 10, 11, 9, 14, 13, 15 }, 329 index = 0, 330 nlen = 0, 331 rhs = 9, lhs = 17; 332 TreeNode *pRoot = NULL; 333 334 nlen = sizeof(arry) / sizeof(int); 335 for ( ; index < nlen; ++index ) 336 InsertNodeToTree( &pRoot, arry[index] ); 337 338 printf( " The data in tree is " ); 339 InOrder( pRoot ); 340 341 index = RecentCommonAncestor( pRoot, lhs, rhs ); 342 printf( " The values of %d and %d ", lhs, rhs ); 343 if ( index == 0 ) 344 printf( "do not have most Recent Common Ancestor. " ); 345 else 346 printf( "have most Recent Common Ancestor: %d. ", index ); 347 348 DestroyTree( &pRoot ); 349 } 350 351 int main() 352 { 353 #if DEBUG 354 printf( "First, we test Tree: " ); 355 TestTree(); 356 357 printf( " Second, we test list: " ); 358 TestList(); 359 #endif 360 361 TestRCA(); 362 363 return 0; 364 }
以前写的时候忘记将思路讲述一下，今天补充下。思路：这里要是基于树的递归结构。在遍历树的过程利用链表将查询节点所经过的路径用链表记录下来（所查节点为开始节点，根节点为末尾戒点），通过两次遍历分别得到两个路径链表。考虑到由于根节点作为链表的末尾节点，那么它们的共同最近最先节点则是两个链表的第一个交叉节点，因此这个问题也就转化为查找两个链表的第一个相交节点。
有关如何有效的记录路径链表：当在树中查找到节点时，返回true，并将节点插入到链表中。这里借助了函数调用过程中栈的使用，即当该函数没有退出时，当前局部数据还在栈中。例如，在递归过程中，当前节点的左右子树没有推出的时候，则在该层函数中，当前节点的数据还保存在系统栈中。