Python의 BST에 주어진 합계의 삼중항이 존재하는지 확인

정수 값과 숫자 '총계'를 포함하는 이진 검색 트리(BST)가 제공된다고 가정합니다. 제공된 BST에 세 개의 요소를 더한 값이 제공된 '총계' 값과 동일한 세 개의 요소 그룹이 있는지 확인해야 합니다.

따라서 입력이 다음과 같으면

total =12이면 출력은 True가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• temp_list :=0으로 초기화된 새 목록
• 트리를 순회하여 temp_list에 넣습니다.
• 0에서 (temp_list의 크기 - 2) 범위에 있는 i에 대해 1씩 증가, 수행
  • 왼쪽 :=i + 1
  • 오른쪽 :=temp_list의 크기 - 1
  • 왼쪽 <오른쪽, do
    • temp_list[i] + temp_list[left] + temp_list[right]가 sum과 같으면
      • 참 반환
    • 그렇지 않으면 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