请教一个算法问题

VIP_fuck

只有截图，大牛指教，这个我没有做出来。

cokeboL

这种比较通用吧

1. Node *findClosestParent(Node *nodeA, Node *nodeB)
   
2. {
   
3.     Node *parentA = nodeA
   
4.     while (parentA)
   
5.     {
   
6.         Node *parentB = nodeB
   
7.         while(parentB)
   
8.         {
   
9.             if(parentA == parentB)
   
10.             {
    
11.                 return parentA
    
12.             }
    
13.             else
    
14.             {
    
15.                 parentB = parentB->parent
    
16.             }
    
17.         }
    
18.         parentA = parentA->parent
    
19.     }
    
20.     return 0;
    
21. }

复制代码

但是题目说了每个node3个child，而且比较规律，一层层从左到右再从右到左，整理下规则算法吧

VIP_fuck

回复 2# cokeboL


    老大，你这是在逗我，，，

VIP_fuck

回复 2# cokeboL


    貌似是没有仔细分析这个问题

    到现在也没想到任意一个节点的子节点怎么得到，已经无数次推翻自己。。

VIP_fuck

顶贴

cokeboL

回复 4# VIP_fuck


怎么得到？

第N层有3^N个Node

从root（第0层）到第N层共有 (3^0 + 3^1 + ... + 3^N)个Node

第N层，N为偶数时按从小到大的顺序从右往左依次分配给N-1层的parent
          N为奇数时按从小到大的顺序从左往右依次分配给N-1层的parent

cokeboL

这个题是说要实现这个数据结构？然后再找出两个Node的最近的祖先？

windoze

回复 6# cokeboL

你这个公式是错的，每个节点都要减掉1，因为root是0，不是3^0

VIP_fuck

各位大牛有时间就看看呗，我是没做出来，，，，用了很长时间，推出来的公式都不对，

VIP_fuck

回复 7# cokeboL


    这个问题就是实现一个接口，输入两个节点，返回节点的最近公共父节点。

    不知道这么说是否清楚。