соединять узлы на одном уровне бинарного дерева

Есть интересный подход, который не использует дополнительную память, что является своего рода индуктивным:

1. Первый уровень уже подключен (у него только один узел)

2. Допустим, уровень i подключен. Затем для подключения уровня i+1 выполните следующие действия:

   а) Инициализируйте узел lst (просто промежуточная переменная, которую мы будем использовать позже) в null

   б) Начните с первого узла на уровне i.

   c) Пройдите узлы на уровне i, начиная с первого узла. Обратите внимание, что вы можете легко перемещаться по узлам на уровне i, потому что он уже подключен, поэтому в каждом узле у вас есть одноуровневые указатели.

   г) Для каждого узла на уровне i сначала посмотрите на его левого потомка, а затем на его правого потомка. Для каждого дочернего элемента, который не равен нулю, если lst не равно null, соедините lst с этим дочерним элементом. Затем установите lst для этого ребенка.

Как только вы подключите уровень i + 1, вы можете перейти на следующий уровень. Если после обхода уровня lst по-прежнему null, это означает, что ни один узел на этом уровне не имел потомка => это был последний уровень, алгоритм можно остановить.

Легко показать, почему это работает, это занимает линейное время и постоянное пространство, так что это строго лучше, чем BFS с очередью (которая требует линейной памяти).

Следуя идее Ишамаэля, я бы предложил процедуру, аналогичную

void link_levels(Tree* t){
    Tree *head, *tail, *end_of_row;
    assert (t != 0);
    t->next = 0;
    head = tail = end_of_row = t;
    while(head != 0){
        if(head->left != 0){
            tail->next = head->left;
            tail = tail->next;
            tail->next = 0;
        }
        if(head->right != 0){
            tail->next = head->right;
            tail = tail->next;
            tail->next = 0;
        }
        if(head == end_of_row){
            head = head->next;
            end_of_row->next = 0;
            end_of_row = tail;
        }
        else {
            head = head->next;
        }
    }
}

Используйте BFS, как предложено в комментариях. Тогда у вас будет расстояние каждого узла от корня.

псевдокод:

 vis[1..n] = false   // mark each node as un-visited
 dis[1..n] = 0
 Queue q
 dis[root] = 0 
 vis[root] = true
 q.push(root)
 while !q.empty()
     node x = q.front()
     children[] = children nodes of node x
     for each child in children 
          !vis[child] 
            dis[child] = dis[x] + 1 
            vis[child] =true 
            q.enqueue(child)
     q.pop()

Теперь у вас будет расстояние каждого узла от корня, агрегирование каждого узла на основе расстояния и возможность соединения узлов в соответствии с вашими требованиями.