Постановка задачи
Вам дано идеальное бинарное дерево, в котором все листья находятся на одном уровне, а у каждого родителя есть два потомка. Бинарное дерево имеет следующее определение:
Пример
Решение
Объяснение
Подход, который я использовал, является рекурсивным, при каждом вызове мы передаем ссылки на левый дочерний элемент и правый дочерний элемент корневого узла. После соединения левого потомка и правого потомка мы снова делаем три рекурсивных вызова, чтобы соединить левое и правое поддеревья левого потомка. Но прежде чем делать вызовы для соединения левого и правого поддеревьев правого дочернего элемента, нам нужно установить связь между правым поддеревом левого дочернего элемента и левым поддеревом правого дочернего элемента.
Рекурсия — это интуитивный подход к решению задач с деревьями. Но итеративный подход также может быть реализован для той же задачи путем обхода порядка уровней. Или с помощью очередей. ✌
