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