与えられた合計のトリプレットがPythonのBSTに存在するかどうかを確認します

整数値と数値「合計」を含む二分探索木（BST）が提供されているとします。提供されたBSTに、3つの要素の加算が提供された「合計」値に等しい、3つの要素のグループがあるかどうかを確認する必要があります。

したがって、入力が次のような場合

total =12の場合、出力はTrueになります。

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

• temp_list：=ゼロで初期化された新しいリスト
• ツリーを順番にトラバースしてtemp_listに配置します
• 0から（temp_listのサイズ-2）の範囲のiの場合、1ずつ増やします。
  • 左：=i + 1
  • right：=temp_listのサイズ-1
  • 左<右、実行
    • temp_list [i] + temp_list [left] + temp_list [right]がsumと同じ場合、
      • Trueを返す
    • それ以外の場合、temp_list [i] + temp_list [left] + temp_list [right]
    • 左：=左+ 1
  • それ以外の場合、
    • right：=right-1

例

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

class TreeNode:
   def __init__(self, value):
      self.value = value
      self.right = None
      self.left = None
def traverse_inorder(tree_root, inorder):
   if tree_root is None:
      return
   traverse_inorder(tree_root.left, inorder)
   inorder.append(tree_root.value)
   traverse_inorder(tree_root.right, inorder)
def solve(tree_root, sum):
   temp_list = [0]
   traverse_inorder(tree_root, temp_list)
   for i in range(0, len(temp_list) - 2, 1):
      left = i + 1
      right = len(temp_list) - 1
      while(left < right):
         if temp_list[i] + temp_list[left] + temp_list[right] == sum:
            return True
         elif temp_list[i] + temp_list[left] + temp_list[right] < sum:
            left += 1
         else:
            right -= 1
   return False
tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
print(solve(tree_root, 12))

入力

tree_root = TreeNode(5)
tree_root.left = TreeNode(3)
tree_root.right = TreeNode(7)
tree_root.left.left = TreeNode(2)
tree_root.left.right = TreeNode(4)
tree_root.right.left = TreeNode(6)
tree_root.right.right = TreeNode(8)
12

出力

True