2017-11-01 9 views
1

レベルの順序で塗りつぶされたバイナリツリーがあるとします。そのレベルのノードの子ノードです。そのようなツリーは、そのレベル順のトラバーサルによって一意に定義できます。例えば、{1,2,3,4,5,6}は{1,2,4,5,3,6}バイナリツリーがレベル順序で塗りつぶされていることを前提とすると、プリオーダートラバーサル配列をレベルオーバトラバーサル配列に変換する(またはその逆)

があり、このの前順走査アレイを生成するであろう

1 
2  3 
4 5 6 

ありますこれらの配列の1つを他の配列に直接変換する方法があります。これは、実際のツリーを生成し、実際のツリーを事前に作成するよりも速いのですか? (ノードがn個のツリーの場合)

+0

これまたは任意の回答があなたの質問を解決した場合は、チェックマークをクリックして受け入れることを検討してください。これは、解決策を見つけたことを広範なコミュニティに示します。これを行う義務はありません。 –

+0

チップをありがとう –

答えて

0

はい、どちらも1回のパスで可能です。

まず、レベルをあらかじめ並べ替えてください。これは少し楽です。これはレベルが満たされたツリーなので、配列内の任意のノードに対して、インデックスがiである場合、左のサブツリーのノードのインデックスの式は2*i+1、右は2*i+2です。だから、私たちはそれらをプリオーダーで再帰的に呼び、希望の配列の後ろにルートノードを追加します。

def level_to_pre(arr,ind,new_arr): 
    if ind>=len(arr): return new_arr #nodes at ind don't exist 
    new_arr.append(arr[ind]) #append to back of the array 
    new_arr = level_to_pre(arr,ind*2+1,new_arr) #recursive call to left 
    new_arr = level_to_pre(arr,ind*2+2,new_arr) #recursive call to right 
    return new_arr 

これをこのように呼び出すと、最後の空白の配列が設定されます。

ans = level_to_pre([1,2,3,4,5,6],0,[]) 

これまでレベルパートに行く前に、dfsはシーンの背後にあるスタックを使用する再帰を使用することを忘れないでください。 bfsがキューを使用する場所。そして、レベル1の順序で配列を配置するという私たちの手の問題は、基本的にはbfsです。したがって、再帰呼び出し(つまりスタック)ではなく、再帰呼び出しをエミュレートするためにキューを明示的に維持する必要があります。

ここでは、サブツリーのルートを指定して、それを最初に配列に追加します。今、上記の問題とは異なり、子ノードのインデックスを見つけることは困難です。左は簡単ですが、ルートの直後になります。右のインデックスを見つけるために、左のサブツリーの合計サイズを計算します。これは、レベルが満たされていることがわかっているため可能です。ここでは、ツリー全体のサイズを指定して、左のサブツリーのサイズを返すヘルパー関数left_tree_size(n)を使用します。したがって、ルートのインデックスを除いて、再帰の場合に渡す第2パラメータはこのサブツリーのサイズです。これを反映するために、(ルート、サイズ)タプルをキューに入れます。

from math import log2 
import queue 

def pre_to_level(arr): 
    que = queue.Queue() 
    que.put((0,len(arr))) 
    ans = [] #this will be answer 
    while not que.empty(): 
     iroot,size = que.get() #index of root and size of subtree 
     if iroot>=len(arr) or size==0: continue ##nodes at iroot don't exist 
     else : ans.append(arr[iroot]) #append to back of output array 
     sz_of_left = left_tree_size(size) 
     que.put((iroot+1,sz_of_left)) #insert left sub-tree info to que 
     que.put((iroot+1+sz_of_left,size-sz_of_left-1)) #right sub-tree info 

    return ans 

最後に、ここでヘルパー関数がありますが、それがなぜ機能するかを理解するためのいくつかの例を示します。

def left_tree_size(n): 
    if n<=1: return 0 
    l = int(log2(n+1)) #l = no of completely filled levels 
    ans = 2**(l-1) 
    last_level_nodes = min(n-2**l+1,ans) 
    return ans + last_level_nodes -1 
関連する問題