小米Git

我的思路是，从0节点开始深度遍历，每次传入目标节点的信息，数组信息，当前节点号和上一个节点号（防止从0遍历到2，对2遍历时又遍历0这种情况）。

每次找的时候，先判断当前节点是否是目标节点，如果是，则记录下当前位置，返回查找成功；如果不是，则对该节点所连的节点进行遍历，如果找到从所连节点处找到目标节点，则记录当前位置，返回查找成功；

对两个目标节点查找完毕后，会形成两个数组，这两个数组的位置信息中从目标节点到根节点的位置信息，从最后开始查找，直到找到两个不同的节点，那么上一个相同的节点，就是需要返回的位置。

int logInfo[2][100] = {0};
int logLoc[2] = {0};
int numNo = 0;
int searchNode( int aimNode, char** matrix, int matrixLen, int loc, int pre)
{
    int i = 0, j = 0;

    if( loc == aimNode)
    {
        logInfo[numNo][logLoc[numNo]] = loc;
        logLoc[numNo]++;
        return 1;
    }
    for( i = 0; i < matrixLen; i++)
    {
        if( i == pre)
        {
            continue;
        }
        if( '1' == matrix[loc][i])
        {
            if( 1 == searchNode(aimNode, matrix, matrixLen, i, loc))
            {
                logInfo[numNo][logLoc[numNo]] = loc;
                logLoc[numNo]++;
                return 1;
            }
        }
    }
    return 0;
}
int Git(char** matrix, int matrixLen, int versionA, int versionB ) {
    // write code here
    int numA = 0; 
    int numB = 0;
    int i = 0;

    searchNode( versionA, matrix, matrixLen, 0, -1);
    numNo++;
    searchNode( versionB, matrix, matrixLen, 0, -1);
    
    numA = logLoc[0] - 1;
    numB = logLoc[1] - 1;
    
    for( i = 0; (i <= numA) && (i <= numB);i++)
    {
        if( logInfo[0][numA - i] != logInfo[1][numB - i])
        {
            return ( logInfo[0][numA - i + 1]);
        }
    }
    
    if ( i == (numA + 1))
    {
        return  logInfo[0][0];
    }
    else 
    {
        return logInfo[1][0];
    }
}