问题描述:

　　算法分析：

　　　　s1：层数对齐:分别求两个数所在的层（l1,l2),把层数大的(假设l2>l1)先往上找父节点，从而对齐到l1层；
　　　　s2：两个数同时往上找, 直到找到公共的父节点（一定能找到，最坏情况下是0), 算法结束。

　　因此算法的核心就变成了如何找父节点, 求父节点的分析:

　　　　求父节点的时候，总是发现没有规律可循， 最重要的原因就是树中节点序号的增加是一个s型的路线，那么我们是利用这种特殊性

（s型），还是去除这种特殊性；我暂时没有发现如何利用这种特殊性， 所以我就先把树中节点的序号按从左到右的顺序递增，发现这样求

父节点的规律就很明显了，所以就采用了"去除这种特殊性"的方法。那么如何去除：每行中间位置上的节点的序号是有规律的，所以通过中

间数，和求得的父节点序号（不是真实的父节点序号， 如：17/3 == 5, 但实际上17的父节点是11,不是5)，得到真实的父节点序号。

　　　　用一个例子来说明, 比如求17的父节点序号：

　　先直接求父节点序号(假的):17/3==5,求父节点所在层(2层）中间节点的序号为8, 所以真实的父节点序号是：8*2-5=11]

//File: Solution.java
//Author: lxw
//Time: 2014-10-09
//Usage: Get the common ancestor.
//Method: Align the layers of the 2 numbers. Decrease both of the layers to find the common ancestor.
//NOTE that each time the layer is decreased, we need to convert the number.

import java.util.*;
public class Solution{
//I really do not think this function uses a good altorithm.
private static int getLayer(int num){
int res = 1;
int last = 0;
int next = 0;
if(num == 0){
return 0;
}
last = (int)((Math.pow(3, res) - 3.0) / 2.0);
while(true){
next = (int)((Math.pow(3, res+1) - 3.0) / 2.0);
if(num > last && num <= next){
return res;
}
++res;
last = next;
}
}

private static int getMid(int layer){  
    if(layer > 0){  
        int sum = 0;  
        for(int i = 1; i < layer; ++i){  
            sum += Math.pow(3, i);  
        }  
        sum += (int)((Math.pow(3, layer) + 1.0) / 2.0);  
        return sum;  
    }  
    else{  
        return 0;  
    }  
}

//num2Lay >= num1Lay  
private static int getCommon(int num2Lay, int num1Lay, int num2, int num1){  
    //层数对齐  
    while(num1Lay != num2Lay){  
        if(num2 % 3 == 0){  
            --num2;  
        }  
        num2 /= 3;  
        --num2Lay;  
        //Each time the layer is decreased, we need to convert the number  
        num2 = 2 \* getMid(num2Lay) - num2;  
    }

    //一起往上找父节点  
    if(num2 == num1){  
        return num1;    //final answer  
    }  
    else{  
        while(num2 != num1){  
            if(num2 % 3 == 0){  
                --num2;  
            }  
            if(num1 % 3 == 0){  
                --num1;  
            }  
            num2 /= 3;  
            num1 /= 3;  
            //Since num2Lay == num1Lay, only one of them is needed.  
            //--num2Lay;  
            --num1Lay;  
            //Each time the layer is decreased, we need to convert the number.  
            int mid = 2 \* getMid(num1Lay);  
            num2 = mid - num2;  
            num1 = mid - num1;  
        }  
        return num1;  
    }  
}

public static void main(String\[\] args){  
    Scanner in = new Scanner(System.in);  
    int num1, num2, num1Lay, num2Lay;  
    while(true){  
        System.out.println("Input:");  
        num1 = in.nextInt();  
        num2 = in.nextInt();  
        num1Lay = getLayer(num1);  
        num2Lay = getLayer(num2);  
        if(num1Lay < num2Lay){  
            System.out.println(getCommon(num2Lay, num1Lay, num2, num1));  
        }  
        else{  
            System.out.println(getCommon(num1Lay, num2Lay, num1, num2));  
        }  
        System.out.println();  
    }  
}  

}

　　写在这里, 如果有人看到话, 希望各位能够互相交流. 肯定有更好的方法, 希望各位不吝赐教.