Поиск обхода PostOrder из обхода LevelOrder без построения дерева

Question

Учитывая двоичное дерево, где значение каждого внутреннего узла равно 1, а листовой узел равен 0. Каждый внутренний узел имеет ровно два ребенка. Теперь данный обход уровня этого дерева возвращает postorder обход одного и того же дерева.

Этот вопрос можно легко решить, если я построю дерево, а затем выполним его обход послепорядка. Хотя это O (n) время. Но возможно ли печатать обход PostOrder без создания дерева.

Answer 1

Это определенно возможно.

Учитывая, что это число Full Binary Tree, как только количество узлов определено, теоретически форма дерева уникальна.

Deem обход заказа уровня в виде массива, например, 1 2 3 4 5 6 7

Она представляет собой такое дерево:

 1 
    2  3 
4 5 6 7 

То, что вы хотите, чтобы получить это обход после заказа : 4 5 2 6 7 3 1.

Первый шаг рассчитать, насколько глубоко дерево:

depth = ceil(log(2, LevelOrderArray.length))  // =3 for this example 

после этого, установите счетчик = 0, и извлечение узлов из нижнего уровня исходного массива, один на один:

for(i=0, i<LevelOrderArray.length, i++){ 
    postOrderArray[i] = LevelOrderArray[ 2^(depth-1) +i ]  //4,5,.... 
    counter++;            //1,2,..... 
} 

Но обратите внимание, что после того, как счетчик может быть разделен на 2, это означает, что вам нужно для получения другого узла от верхнего уровня:

if(counter mod 2^1 == 0) 
    postOrderArray[i] = LevelOrderArray[ 2^(depth -2) + (++i) ]  // =2 here, 
//which is the node you need after 4 and 5, and get 3 after 6 and 7 at the 2nd round 

не ++ счетчика здесь, потому что счетчик представляет сколько узлов вы извлечены из нижнего уровня.

Каждый раз, когда 2^2 = 4 узлов было выскочить, получить еще один узел из 3-го уровня (считая от дна)

if(counter mod 2^2 == 0) 
    postOrderArray[i] = LevelOrderArray[ 2^(depth -3) + (++i) ]  // =1 

Каждый раз, когда 2^3 = 8 узлов было выскочить, опять же, получить другое узел с 4-го уровня

.... пока цикл не закончен.

Это не строгий код на C++, только концепция. Если вы полностью понимаете алгоритм, значение узлов дерева вообще не имеет значения, хотя есть все 0 и 1. Дело в том, что вы не создали дерево в программе, но создайте его в своем вместо этого, и превратить его в алгоритм.