Boundary Traversal of Binary Tree
配列 root には、二分木がレベル順で格納されています。根はインデックス 0 にあり、インデックス i のノードの子は 2i+1（左）と 2i+2（右）です。空の位置には -1 を使い、末尾に余分な -1 の要素が含まれる場合もあります。葉とは、子を持たないノードです。
根から反時計回りに境界を返してください。
- 根。
- 左境界（上から下へ）：根の左の子から始め、左の子があれば左の子へ、なければ右の子へ進みます。葉の手前で止めます。
- すべての葉（左から右へ）。
- 右境界（下から上へ）：左境界を反転したものを、根の右の子からたどります。
同じノードを2回列挙しないため、ノードが1つだけの木では根だけを返します。
関数
- rootinteger-array
- 空の位置には -1 を使い、二分木をレベル順に
- 戻り値integer-array
- 境界値を、根から反時計回りに
制約
1 ≤ root.length ≤ 32767- 各
root[i]は-1、または0 ≤ root[i] ≤ 105を満たす値です。 root[0]は決して-1ではないため、木には少なくとも 1 つのノードがあります。- 配列は、最後のノードの後に余分な
-1エントリが続いて終わる場合があります。 - 空の位置の子はどちらも空であり、深さは最大でも
14です。 - ノードの値はそれぞれ異なります。
例
- 入力
- root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
- 出力
- [7, 3, 1, 4, 6, 8, 9]
- 説明
- ルートの
7の後、左境界は3です。その子の1は葉です。葉は1、4、6、8です。右境界は9で、葉の8の上にあります。
- 入力
- root = [10, 4, -1, -1, 6, -1, -1, -1, -1, 5, 8]
- 出力
- [10, 4, 6, 5, 8]
- 説明
4には左の子がないため、左境界は6に移り、その後、葉5で止まります。葉5、8が続きます。根には右の子がありません。
- 入力
- root = [3]
- 出力
- [3]
- 説明
- ルートはツリー全体です。これは一度だけ記載され、葉として再び記載されることはありません。
発展問題
境界を時計回りに列挙するにはどうすればよいでしょうか。ルート、右端を上から下へ、葉を右から左へ、その後左端を下から上へ、という順ですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
答えを4つの部分に分けます。根、左端、葉、右端です。これらのうち、木を下る単一路で済むものと、全体を走査する必要があるものはどれでしょうか？
各エッジは1つの経路です。根の子から始め、その側の子へ進み続けます。その側が空の場合は、もう一方の子へ進みます。左から右への順に並ぶ葉は、左部分木を先に訪問する深さ優先探索によって得られます。接続部分に注意してください。エッジの終点となる葉も、葉に含まれます。
インデックス
1から下へたどり、各非葉ノードを追加します。次に、先行順走査ですべての葉ノードを追加します。その後、インデックス2から下へたどり、各非葉ノードを収集し、そのリストを逆順に追加します。
解説
答えは4つの部分をつなげたものです。ルート、左端に沿って下る経路、左から右へ並べた葉、そして逆順に読んだ右端に沿って下る経路です。つなぎ目では、端の経路の終点となる葉と、葉であるルートを、それぞれ一度だけ列挙します。
3つのパートを個別に確認する
考え方
各辺はそれぞれ1つの経路です。根の子から始めて、次のノードが葉になる直前までノードを列挙します。その葉は葉の部分で列挙するためです。左を右より先にたどる先行順走査では、葉を左から右の順に訪れます。深さに関係なく、左部分木のすべてのノードは右部分木の左側にあるためです。右端の辺を上から順に集め、逆順にして追加します。
各辺ではそれぞれ1つの経路をたどり、葉の走査では各ノードを1回ずつ訪れるため、時間計算量は O(n) で、再帰の深さは h レベルです。
アルゴリズム
- ルートから始めます。ルートが葉なら、それを返します。
- インデックス
1から始め、ノードが存在し、葉でない間は、そのノードを追加して左の子へ進みます。左の子がなければ右の子へ進みます。 - インデックス
1と2から、左を先にして先行順にたどり、すべての葉を追加します。 - インデックス
2から、ステップ2と同様に、右の子を優先してノードを集めます。 - 集めたノードを逆順に追加します。
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
def is_leaf(i):
return not real(2 * i + 1) and not real(2 * i + 2)
result = [root[0]]
if is_leaf(0):
return result
# 1. The left boundary, top-down, stopping before its leaf.
i = 1
while real(i) and not is_leaf(i):
result.append(root[i])
i = 2 * i + 1 if real(2 * i + 1) else 2 * i + 2
# 2. Every leaf: a pre-order walk meets them from left to right.
def add_leaves(i):
if not real(i):
return
if is_leaf(i):
result.append(root[i])
return
add_leaves(2 * i + 1)
add_leaves(2 * i + 2)
add_leaves(1)
add_leaves(2)
# 3. The right boundary, collected top-down and added bottom-up.
right = []
i = 2
while real(i) and not is_leaf(i):
right.append(root[i])
i = 2 * i + 2 if real(2 * i + 2) else 2 * i + 1
result.extend(reversed(right))
return resultエッジフラグを使った1回の先行順走査
考え方
各ノードにフラグを付けて、スタック上で走査を1回の先行順走査にまとめます。左端の辺上では1、右端の辺上では2、内側では0を付けます。ルートの子にはそれぞれ1と2を付けて開始します。辺上のノードは、その側にある子、または唯一の子にフラグを引き継ぎます。それ以外の子には0を付けます。2つ目の例では、1は4から6、そして5へと引き継がれます。
ノードをスタックから取り出すたびに、すべての葉と、フラグが1の葉以外のノードを追加します。フラグが2の葉以外のノードは集めて、最後に逆順で追加します。先行順走査では、どの葉よりも先に左端の辺上のすべてのノードに到達します。これは、辺が右に曲がるのは、その左側に何もない場所だけだからです。
アルゴリズム
- ルートから始めます。右の子をフラグ
2でプッシュし、次に左の子をフラグ1でプッシュします。 - ノードをポップします。葉であるか、フラグ
1を持つ場合は追加します。フラグ2を持つ非葉ノードは右側のリストに追加します。 - 右の子をプッシュし、次に左の子をプッシュします。それぞれにルールで指定されたフラグを付けます。
- スタックが空になったら、右側のリストを逆順にして追加します。
def boundaryTraversal(root):
n = len(root)
def real(i):
return i < n and root[i] != -1
result = [root[0]]
right = [] # the right boundary, top-down; it goes on the end reversed
# Each entry is (index, edge): 1 = left boundary, 2 = right boundary, 0 = inside.
stack = []
if real(2):
stack.append((2, 2))
if real(1):
stack.append((1, 1))
while stack:
i, edge = stack.pop()
has_left, has_right = real(2 * i + 1), real(2 * i + 2)
if not has_left and not has_right:
result.append(root[i]) # a leaf; pre-order meets them left to right
elif edge == 1:
result.append(root[i]) # the left boundary, top-down
elif edge == 2:
right.append(root[i])
# An edge passes to the child on its own side, or to an only child.
# The right child goes on the stack first, so the left one comes out first.
if has_right:
stack.append((2 * i + 2, edge if edge == 2 or not has_left else 0))
if has_left:
stack.append((2 * i + 1, edge if edge == 1 or not has_right else 0))
result.extend(reversed(right))
return result
落とし穴と境界ケース
- ノードを2回列挙する。葉に達する前に止まらないエッジ走査では、例1で
1を2回列挙し、ノードが1つだけの木では、根を葉として再び列挙してはならない。 - 各レベルの最初のノードを左境界とする。根の左の子が葉で、右部分木のほうが深い場合、深いレベルは右部分木のノードから始まるが、左境界は空になる。
- 左の子だけをたどる。例2では、境界は
4からその右の子6へ進まなければならない。 - 葉をレベルごとに集める。すると例1では
1、8、4、6となる。 - LuaとRでは、
2i+1の計算のためにノードのインデックスを0始まりのままにし、root[i + 1]を読み取る。
よくある質問3
二分木の境界走査とは何ですか？
木の輪郭を反時計回りに列挙します。根、上から下への左端、左から右への葉、そして下から上への右端です。端の部分からは葉が除かれるため、同じノードが2回現れることはありません。
境界走査の時間計算量はどれくらいですか？
O(n)。2つの端の走査はそれぞれ1つの経路をたどり、葉の走査ではすべてのノードを1回ずつ訪れます。追加の空間計算量は、再帰またはスタックのためのO(h)です。
左の境界は常に左の子に沿いますか？
いいえ。左の子がある場合は左の子へ移動し、そうでない場合は右の子へ移動します。左側から見たときに見える最も外側の経路です。ルートに左の子がない場合、左境界は空です。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def boundaryTraversal(root):
# ここにコードを記述してくださいテスト #1
テスト #2
テスト #3
引数
root = [7, 3, 9, 1, 5, 8, -1, -1, -1, 4, 6]
期待される出力
[7, 3, 1, 4, 6, 8, 9]