Середина

Проблема

Учитывая бинарное дерево

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Заполните каждый следующий указатель, чтобы он указывал на его следующий правый узел. Если нет следующего правого узла, следующий указатель должен быть установлен на NULL.

Изначально все следующие указатели установлены на NULL.

Примечание.

  • Вы можете использовать только постоянное дополнительное пространство.
  • Рекурсивный подход хорош, неявное пространство стека не считается дополнительным пространством для этой проблемы.
  • Вы можете предположить, что это идеальное бинарное дерево (т. е. все листья находятся на одном уровне, и у каждого родителя есть два потомка).

Пример:

Учитывая следующее совершенное бинарное дерево,

    1
   /  \
  2    3
 / \  / \
4  5  6  7

После вызова вашей функции дерево должно выглядеть так:

    1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

Решение

Обрабатывайте дочернюю метку next каждого узла уровень за уровнем.

Сложность

Мы тривиально повторяем каждый узел один раз, поэтому его временная сложность составляет O(n), где n обозначает количество узлов в этом дереве. Также очевидно, что используется только O(1) дополнительного пространства.