BSTの各内部ノードにPythonで子が1つだけあるかどうかを確認します

二分探索木（BST）のプレオーダートラバーサルがあるとします。各内部ノードに子が1つしかないかどうかを確認する必要があります。

したがって、入力がpreorder =[22、12、13、15、14]のようである場合、BSTは-

これを解決するために、1つの効率的なアプローチに従うことができます。ノードのすべての子孫は小さいか大きいので、次の手順に従うことができます-

• ノードの次のプレオーダーサクセサを取得します

• ノードの最後のプレオーダーサクセサを取得します

• 両方のサクセサが現在のノードよりも小さいか大きい場合は、もう一度チェックしてください。そうでない場合はfalseを返します。

これを解決するには、次の手順に従います-

• 次：=0、最後：=0
• iの範囲が0からプレオーダーのサイズ-1、do
  • next：=preorder [i]-preorder [i + 1]
  • last：=preorder[i]-preorderの最後の値
  • next * last <0の場合、
    • Falseを返す
• Trueを返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(preorder):
next = 0
last = 0
for i in range(len(preorder)-1):
next = preorder[i] - preorder[i+1]
last = preorder[i] - preorder[-1]
if next * last < 0:
return False
return True
preorder = [22, 12, 13, 15, 14] print(solve(preorder))

入力

[22, 12, 13, 15, 14]

出力

True