Python
 Computer >> コンピューター >  >> プログラミング >> Python

配列がPythonで二分探索木の順序を表しているかどうかを確認します

numsと呼ばれる数値の配列があるとします。配列が二分探索木の要素を順番にトラバーサルする順序で保持しているかどうかを確認する必要があります。

したがって、入力がnums =[5、8、15、18、20、26、39]のような場合、これは順序どおりのトラバーサルであるため、出力はTrueになります

配列がPythonで二分探索木の順序を表しているかどうかを確認します

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

  • size：=numsのサイズ
  • サイズが0または1の場合、
    • Trueを返す
  • iの範囲が1からサイズ-1の場合、実行します
    • nums [i-1]> nums [i]の場合、
      • Falseを返す
  • Trueを返す

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

例

def solve(nums):
   size = len(nums)
   if size == 0 or size == 1:
      return True
   for i in range(1, size):
      if nums[i - 1] > nums[i]:
         return False
   return True
nums = [5, 8, 15, 18, 20, 26, 39] 
print(solve(nums))

入力

[5, 8, 15, 18, 20, 26, 39]

出力

True

  1. Pythonのバイナリ検索ツリーの最も低い共通の祖先

    二分探索木があるとします。与えられた2つのノードの中で最も低い共通の祖先ノードを見つける必要があります。 2つのノードpとqのLCAは、実際には、pとqの両方を子孫として持つツリーの最下位ノードです。したがって、二分木が[6、2、8、0、4、7、9、null、null、3、5]のような場合。ツリーは次のようになります- ここで、2と8のLCAは6です これを解決するには、次の手順に従います- ツリーが空の場合は、nullを返します pとqの両方がrootと同じ場合は、rootを返します left：=pとqを使用したルートの左側のサブツリーのLCA right：=pとqを使用し

  2. ソートされた配列をPythonでバイナリ検索ツリーに変換する

    ソートされた配列Aが1つあるとします。高さのバランスが取れた2分探索を1つ生成する必要があります。この問題では、高さのバランスが取れた二分木は、実際には、すべてのノードの2つのサブツリーの深さが1を超えて異ならない二分木です。配列が[-10、-3、0、5、9のようであるとします。 ]。したがって、考えられる出力の1つは、[0、-3、9、-10、null、5]のようになります。 これを解決するために、次の手順に従います。 Aが空の場合は、Nullを返します 中間要素を見つけて、ルートにします 配列を2つのサブ配列、中央要素の左側と中央要素の右側に分割します 左側のサブアレイと右側のサ