Binary Tree Zigzag Level Order Traversal
配列 root に格納された二分木が与えられます。根はインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあります。-1 は空の位置を示し、配列の末尾には余分な -1 が含まれる場合があります。
ノードの値を、レベルごとにジグザグ順で返してください。根のレベルは左から右へ、次のレベルは右から左へというように、最も深いレベルまで交互にたどります。これはスパイラルレベル順走査とも呼ばれます。
関数
- rootinteger-array
- ヒープ順序で表した木。空の位置には -1
- 戻り値integer-2d-array
- レベルごとに値のリストが1つずつあり、最上位レベルから始めて、左から右、右から左の順に交互に並びます
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1または0 ≤ root[i] ≤ 104を満たす値です。 - ノードの値はそれぞれ異なります。
root[0]は決して-1ではないため、木には少なくとも1つのノードがあります。- 配列の末尾には、最後のノードの後に余分な
-1の要素が含まれる場合があります。 - 空の位置の子もどちらも空で、木のレベル数は最大でも
14です。
例
- 入力
- root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
- 出力
- [[8], [5, 12], [1, 9, 14], [11, 2, 4]]
- 説明
- 左から右へ読むと、各レベルは
8;12, 5;1, 9, 14;4, 2, 11です。レベル1と3は逆方向に進みます:[5, 12]と[11, 2, 4]。
- 入力
- root = [1, 2, 3, 4, 5, 6, 7, -1, -1]
- 出力
- [[1], [3, 2], [4, 5, 6, 7]]
- 説明
- 3階層の完全な木です。中間の階層は
[3, 2]に反転し、第3階層は再び左から右へ進みます。末尾の-1の2つのエントリは、4の空の子ノードの位置です。
- 入力
- root = [5]
- 出力
- [[5]]
- 説明
- 単一のノードは、どちらの方向から読んでも、1つの値の1つのレベルです。
発展問題
すべての値を逆順にしたり、2つ目のスタックを使ったりせず、各行の最終的な位置に直接配置できますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
まず、通常のレベル順走査のように、各レベルを左から右へ集めます。それらのリストのうち、どれをどのように変更する必要がありますか？
根を 0 として各レベルに番号を付けます。奇数レベルは逆方向に読みます。リストを逆順にするにはリストを読むのと同じだけのコストがかかるため、それらのレベルを逆順にしても全体の処理は線形時間です。
反転を省略するには、現在のレベルをスタックに保持し、要素を取り出すときに子ノードを別のスタックに追加します。左から右へ読み取るときは左の子ノードを先に、右から左へ読み取るときは右の子ノードを先に追加します。すると、別のスタックから取り出すことで、次のレベルを必要な順序で処理できます。
解説
各レベルは通常の幅優先探索で得られます。新しい点は方向です。レベルごとに、交互に逆順になります。各レベルを作成した後で奇数番目の行を逆順にするか、各レベルをスタックに保持します。スタックは、プッシュした順序とは逆の順序で項目を取り出します。
レベル順に並べ、その後、1つおきのレベルを逆順にする
考え方
キューを使って1ラウンドに1つのレベルを処理すると、各レベルの要素を左から右へ取得できます。根をレベル0として番号を付けると、ジグザグ順では奇数レベルが右から左に並ぶため、それらの行だけを反転すれば答えが得られます。
探索では各ノードを1回ずつ訪問し、反転では各値にもう1回ずつ触れるため、時間計算量は O(n) です。
アルゴリズム
- インデックス
0でキューを開始します。 - 各ラウンドで、キューの長さ
sを保存し、s個のインデックスをデキューして新しい行に入れ、それぞれの既存の子を左から右の順にエンキューします。 - 答えにすでに奇数個の行が含まれている場合は、その行を逆順にします。
- その行を追加し、キューが空になるまで続けます。
from collections import deque
def zigzagLevelOrder(root):
n = len(root)
levels = []
queue = deque([0]) # node indexes; the root is never empty
while queue:
row = []
for _ in range(len(queue)): # exactly the nodes of the current level
i = queue.popleft()
row.append(root[i])
for child in (2 * i + 1, 2 * i + 2):
if child < n and root[child] != -1:
queue.append(child)
if len(levels) % 2 == 1: # levels 1, 3, 5, ... read from right to left
row.reverse()
levels.append(row)
return levels2つのスタック
考え方
現在のレベルをスタックに保持し、レベルを読む方向に取り出します。取り出した各ノードの子を2つ目のスタックに積みます。現在のスタックが空になると、2つ目のスタックに次のレベルが格納されています。
積む順序によってこれが機能します。左から右へ取り出す場合は、各ノードの左の子、次に右の子を積みます。最も右のノードの右の子が最後に積まれるため、次のレベルは右端から取り出されます。右から左へ取り出す場合は、右、次に左の順に積みます。最も左のノードの左の子が最後に積まれます。
例1：8を取り出し、12, 5を積みます。5, 12を取り出し、次に5から14、12から9, 1を積みます。1, 9, 14を取り出し、次に9から4, 2、14から11を積みます。11, 2, 4を取り出します。
各ノードは1回ずつ積まれ、1回ずつ取り出されます。反転処理なしで、時間計算量はO(n)です。
アルゴリズム
- ルートのインデックス
0をスタックにプッシュし、左から右へ読み始めます。 - スタックが空でない間、すべてのインデックスをポップして新しい行に入れ、ポップした各ノードの既存の子を2つ目のスタックにプッシュします。左から右へ読む場合は左、次に右の順で、それ以外の場合は右、次に左の順でプッシュします。
- その行を答えに追加します。
- 2つ目のスタックを現在のスタックにし、方向を反転して繰り返します。
def zigzagLevelOrder(root):
n = len(root)
levels = []
current = [0] # a stack of node indexes; the root is never empty
left_to_right = True
while current:
row = []
upcoming = [] # the next level, pushed while this one pops
while current:
i = current.pop()
row.append(root[i])
# Push so that the next level pops out in its own direction.
if left_to_right:
children = (2 * i + 1, 2 * i + 2)
else:
children = (2 * i + 2, 2 * i + 1)
for child in children:
if child < n and root[child] != -1:
upcoming.append(child)
levels.append(row)
current = upcoming
left_to_right = not left_to_right
return levels
落とし穴と境界ケース
- 子ノードが単一のキューに入る順序を反転すること。兄弟ノードの順序は入れ替わりますが、親ノードの順序は変わりません。例1の第3レベルは
[9, 1, 14]になります。 - レベルを1から数えること。反転するたびにレベルが1つずれ、例1では
[[8], [12, 5], [14, 9, 1], [4, 2, 11]]になります。 - 2つのスタックを使う方法で、すべてのレベルに同じプッシュ順序を使うこと。すると例1の第3レベルは
[9, 1, 14]の順にポップされます。 - ポップ中のスタックに子ノードをプッシュすること。子ノードは、親のレベルに残っている他のノードより先に取り出されます。
- 行を逆順にする代わりにソートすること。例1の最後のレベルは
[11, 2, 4]でなければならず、どのようにソートしてもこの順序にはなりません。
よくある質問3
ジグザグ順走査とレベル順走査の違いは何ですか？
同じノードを持つ同じレベルを訪れます。レベル順では各レベルを左から右へ読み取り、ジグザグ順ではルートの下のレベルから始めて、1つおきのレベルを右から左へ読み取ります。どちらも O(n) 時間で実行されます。
ジグザグ走査は、木のらせん順走査と同じですか？
はい、この2つの名前は同じ走査を表しています。テキストによっては、第2レベルを右ではなく左から始めるものもありますが、反転するレベルが1つずれるだけです。ここでは、ルートのレベルは左から右へ進み、次のレベルは右から左へ進みます。
両端キューでジグザグ順のレベル順走査はできますか？
はい。両端キューでは、各レベルのノードを左から右の順に並べます。左から右に進むレベルでは、先頭からノードを取り出し、その子を左、次に右の順で末尾に追加します。右から左に進むレベルでは、末尾からノードを取り出し、その子を右、次に左の順で先頭に追加します。各ラウンドの開始時に取得する数が、引き続きそのレベルを示します。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def zigzagLevelOrder(root):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [8, 12, 5, 1, 9, -1, 14, -1, -1, 4, 2, -1, -1, 11]
期待される出力
[[8], [5, 12], [1, 9, 14], [11, 2, 4]]