Subtree of Another Tree
2 つの二分木 root と subRoot が与えられます。それぞれレベル順の配列に格納されています。根はインデックス 0 にあり、インデックス i の子は 2*i+1（左）と 2*i+2（右）にあり、空の位置には -1 が入っています。配列の末尾には余分な -1 の要素が含まれる場合があります。
root のいずれかのノードとそのすべての子孫が、subRoot と形状および値が完全に一致する場合は true を返し、そうでなければ false を返してください。root 全体が一致する場合も含みます。
関数
- rootinteger-array
- 検索する木を、空の位置を -1 で表し、レベル順に
- subRootinteger-array
- 探す対象の木を、同じ形式で
- 戻り値boolean
- subRoot が root 内にすべての子孫を伴うノードとして現れる場合は true、それ以外の場合は false
制約
1 ≤ root.length ≤ 32767および1 ≤ subRoot.length ≤ 32767- 各エントリは
-1、または0から104までの値です。 root[0]とsubRoot[0]は決して-1ではないため、どちらの木にも少なくとも1つのノードがあります。- どちらの配列も、最後のノードの後に余分な
-1の要素が続く場合があります。 - 空の場所の子も両方とも空で、各木の深さは最大でも
14です。 - 値は繰り返されることがあります。
例
- 入力
- root = [6, 2, 8, 1, 3, -1, 9]subRoot = [2, 1, 3]
- 出力
- true
- 説明
- インデックス
1のノード2には、子1と3があり、どちらも葉です。これがまさにsubRootです。
- 入力
- root = [6, 2, 8, 1, 3, -1, 9, -1, -1, 0]subRoot = [2, 1, 3]
- 出力
- false
- 説明
- ノード
2の下にある3には、子ノード0ができました。部分木にはすべての子孫が含まれるため、ノード2はsubRootの3個に対して4個のノードを持ち、ほかに2を持つノードはありません。
- 入力
- root = [5, 5, 7]subRoot = [5]
- 出力
- true
- 説明
- 根の
5には子が2つあるため、単一のノード5とは一致しません。インデックス1にある5は葉であり、一致します。
発展問題
各部分木の値と子のフィンガープリントから、その部分木ごとにフィンガープリントを作成して、subRootとの比較をO(1)で行えるでしょうか？異なる2つの部分木で衝突が起きた場合はどうしますか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
subRootがrootの中に現れる場合、その最上部はrootのいずれかのノードに位置します。それはどのノードである可能性があり、そこで何を確認しますか？2つの木が同一かどうかを判定する関数を書きましょう。どちらも空であるか、頂点の値が同じで、左部分木と右部分木がそれぞれ同一である必要があります。一方が空で、もう一方が実際のノードであれば、それらは異なります。
rootの各ノードでそのチェックを実行します。大半のノードをスキップするには、まず各ノードの高さを計算します。高さがsubRootの高さと等しいノードだけが一致する可能性があります。
解説
この問題には 2 つの部分があります。2 つの木が同一かどうかを判定することと、root のどこでその判定を行うかを選ぶことです。高さが subRoot の高さと等しいノードだけが一致する可能性があり、同じ高さのノード同士は重ならないため、それらだけを調べれば root の各ノードを最大 1 回だけたどることになります。
各ノードで比較する
考え方
i が配列の範囲内にあり、その位置の値が -1 でない場合、その位置は実在します。2つの木は、両方とも空であるか、または頂点の値が同じで、左部分木と右部分木がそれぞれ同一である場合に同一です。same(i, j) は、i からの root と j からの subRoot を同時にたどります。subRoot が root に現れるなら、その頂点は何らかのノード上に位置するため、実在する i すべてについて same(i, 0) を試します。
各 n 個のノードから、近い一致は失敗するまで最大 m ステップ続くことがあります。つまり O(n·m) です。ここでは深さの上限によって制限されます。あるノードがたどられるのは、そのノードまたはその上から始まるチェックだけであり、最大でも 14 回です。
アルゴリズム
same(i, j)を記述します。rootの位置iとsubRootの位置jがどちらも空なら、trueを返します。片方だけが空なら、falseを返します。- 2つの値が異なる場合は、
falseを返します。そうでなければ、same(2*i+1, 2*j+1)とsame(2*i+2, 2*j+2)を返します。 rootの実際のインデックスiについて、same(i, 0)が成り立つものがあればtrueを返し、そうでなければfalseを返します。
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
# Try every real node of root as the top of a match.
for i in range(n):
if root[i] != -1 and same(i, 0):
return True
return False高さが一致する場合にのみ比較します
考え方
同一の木は高さが同じです。高さは、最長経路上のノード数として数えます。そのため、確認する価値があるのは、高さがsubRootの高さと等しいrootのノードだけです。最初の例では、subRootの高さは2で、rootでは2と8だけが該当します。
あるノードは、その下にあるすべてのノードより高いため、高さが等しい2つのノードが互いの内側に位置することはありません。各確認では開始ノードの部分木だけをたどるので、すべての確認を合わせても、rootの各ノードをたどるのは最大1回です。
子は親より大きなインデックスに位置するため、最後のインデックスから逆順に走査すると、親より先に両方の子に到達します。2回の高さの走査と確認にかかる時間はO(n + m)です。
アルゴリズム
- 各木の高さ配列を、最後のインデックスから
0まで逆順に走査して埋めます。空の位置は0、実際のノードは、2つの子のうち高い方の高さに1を加えた値です。 rootの各インデックスiについて、その高さがsubRootのインデックス0の高さと等しい場合は、same(i, 0)を実行し、条件を満たせばtrueを返します。falseを返します。
def isSubtree(root, subRoot):
n, m = len(root), len(subRoot)
def same(i, j):
# True if the subtree at root[i] equals the subtree at subRoot[j].
a = i < n and root[i] != -1
b = j < m and subRoot[j] != -1
if not a or not b:
return a == b # two empty spots match, one empty spot does not
if root[i] != subRoot[j]:
return False
return same(2 * i + 1, 2 * j + 1) and same(2 * i + 2, 2 * j + 2)
def heights(tree):
# Children sit at larger indexes, so a backward scan finishes them first.
h = [0] * len(tree)
for i in range(len(tree) - 1, -1, -1):
if tree[i] != -1:
left = h[2 * i + 1] if 2 * i + 1 < len(tree) else 0
right = h[2 * i + 2] if 2 * i + 2 < len(tree) else 0
h[i] = 1 + max(left, right)
return h
target = heights(subRoot)[0]
rootHeights = heights(root)
# Only a node of the same height can match, and no two such nodes overlap.
for i in range(n):
if rootHeights[i] == target and same(i, 0):
return True
return False
落とし穴と境界ケース
- 2番目の例のように、一部分だけ一致していても受け入れてしまうこと。
rootにノードがあり、subRootの同じ位置が空欄の場合、sameは失敗しなければなりません。 - 値が一致する最初のノードで探索を止めてしまうこと。3番目の例では、ルートの
5は一致せず、その下にある葉の5が一致します。 - 2つの配列のスライスを比較すること。部分木のノードは複数の階層にまたがり、どちらの配列も末尾に余分な
-1が含まれることがあります。配列の末尾を越えたインデックスは、-1と同様に空欄です。 - LuaとRでは、
2*i+1の計算に合わせてノードのインデックスを0始まりのままにし、root[i + 1]を読み取ります。
よくある質問3
別の木の部分木の時間計算量はどのくらいですか？
すべてのノードから比較すると、最悪の場合の計算量は O(n·m) です。ここで、n と m は2つの木のサイズです。高さが subRoot の高さと等しいノードでのみ比較すると、O(n + m) になります。これは、その場合 root の各ノードをたどる回数が最大1回になるためです。
別の木の部分木は文字列マッチングで解けるでしょうか？
はい。各木を先行順で記述し、空の子ごとに#を使い、各値の前に区切り文字を入れます: ,2,1,#,#,3,#,#。subRootが部分木であるのは、その文字列がrootの文字列内に現れる場合に限ります。また、KMPを使えばO(n + m)で見つけられます。マーカーがないと異なる形の木が同じ文字列になります。区切り文字がないと、12に2が含まれてしまいます。
subRoot と一致するノードに追加の子ノードがある場合も一致すると見なされますか？
いいえ。部分木とは、あるノードとそのすべての子孫ノードのことなので、一致したノードの下にあるすべてのノードも subRoot に含まれていなければなりません。2つ目の例では、3 の下に余分な 0 があるため、答えは false になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def isSubtree(root, subRoot):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
root = [6, 2, 8, 1, 3, -1, 9] subRoot = [2, 1, 3]
期待される出力
true