在不構造樹的情況下從LevelOrder遍歷中查找PostOrder遍歷

Question

給定一個二叉樹，其中每個內部節點的值爲1且葉節點爲0.每個內部節點 恰好有兩個子節點。現在給出了這棵樹的水平順序遍歷，並且返回同一棵樹的遍歷樹。

這個問題可以很容易地解決，如果我構造一棵樹，然後做它的後序遍歷。雖然是O（n）時間。但是是否可以在不構建樹的情況下打印postOrder遍歷。

Answer 1

這絕對有可能。

考慮到它是Full Binary Tree，一旦確定了節點的數量，理論上樹的形狀就是唯一的。

認爲水平序遍歷作爲陣列，例如，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個節點是蹦出，檢索從第三電平的另一節點（從底部算起）

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

每次2^3 = 8個節點是蹦出，再次檢索另一個從第4級開始的節點

....直到循環結束。

這不是嚴格的C++代碼，只是概念。如果你完全理解這個算法，樹節點的值根本就不重要，即使它們全都是0和1.雖然你並沒有在程序中建立樹，但是在你的程序中建立了它，但是相反，轉換成算法。