My Hackerrank Solution of Swap Nodes [Algo]

click here to the problem description.

C solution without using tree structure

The tricky thing here is : we can pre/in/post/order traverse the “tree” by the indexes itself, and what we always swap are only some groups of two children at some given depth.

What I did is recording depth of every “index” or say, node, using a recursive function:

int markd(int** i, int *depth, int d, int node) {
    depth[node - 1] = d;
    int r = d, l = d;
    if (-1 != i[node - 1][0])
        l = markd(i, depth, d + 1, i[node - 1][0]);
    if (-1 != i[node - 1][1])
        r = markd(i, depth, d + 1, i[node - 1][1]);
    return l > r ? l : r;
}

This recursive function also returns the max deep, which is useful for finding matching of each queries.

Then we need an in-order recursive function to record the result of each queries :

void mid(int **i, int node, int *arr, int *ia) {
    if (-1 != i[node - 1][0])
        mid(i, i[node - 1][0], arr, ia);
    arr[(*ia)++] = node;
    if (-1 != i[node - 1][1])
        mid(i, i[node - 1][1], arr, ia);
}

Then put it altogether, I bind the allocations and query caculations into one pass.

int** swapNodes(int indexes_rows, int indexes_columns, int** indexes, int queries_count, int* queries, int* result_rows, int* result_columns) {
    /*
     * Write your code here.
     */
    int **ans = malloc(sizeof(int*) * queries_count);
    int *depth = malloc(sizeof(int) * indexes_rows);
    int maxd;

    *result_rows = queries_count;
    *result_columns = indexes_rows;

    maxd = markd(indexes, depth, 1, 1);
    for (int i = 0; i < queries_count; i++) {
        ans[i] = malloc(sizeof(int) * indexes_rows);
        for (int j = queries[i]; j <= maxd; j += queries[i]) {
            for (int k = 0; k < indexes_rows; k++) {
                if (depth[k] == j) {
                    int temp = indexes[k][0];
                    indexes[k][0] = indexes[k][1];
                    indexes[k][1] = temp;
                }
            }
        }
        int ridx = 0;
        mid(indexes, 1, ans[i], &ridx);
    }

    free(depth);
    return ans;
}