ตรวจสอบว่ามีแฝดสามที่มีผลรวมที่กำหนดใน BST ใน Python

สมมติว่าเราได้รับ Binary Search Tree (BST) ที่มีค่าจำนวนเต็มและ 'ผลรวม' ตัวเลข เราต้องค้นหาว่ามีกลุ่มขององค์ประกอบสามอย่างใน BST ที่ให้มาหรือไม่ โดยที่การเพิ่มองค์ประกอบทั้งสามนั้นเท่ากับค่า 'รวม' ที่ให้มา

ดังนั้นหากอินพุตเป็นแบบ

รวม =12 แล้วผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• temp_list :=รายการใหม่ที่เริ่มต้นด้วยศูนย์
• inorder สำรวจต้นไม้และใส่ไว้ใน temp_list
• สำหรับฉันในช่วง 0 ถึง (ขนาดของ temp_list - 2) เพิ่มขึ้น 1 ทำ
  • ซ้าย :=ผม + 1
  • ขวา :=ขนาดของ temp_list - 1
  • ขณะซ้าย <ขวา ทำ
    • ถ้า temp_list[i] + temp_list[left] + temp_list[right] เท่ากับผลรวม ดังนั้น
      • คืนค่า True
    • มิฉะนั้นเมื่อ temp_list[i] + temp_list[left] + temp_list[right] <ผลรวมไม่เป็นศูนย์ ดังนั้น
      • ซ้าย :=ซ้าย + 1
    • มิฉะนั้น
      • ขวา :=ขวา - 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