Python에서 BST의 각 내부 노드에 정확히 하나의 자식이 있는지 확인하십시오.

이진 탐색 트리(BST)의 선주문 순회가 있다고 가정합니다. 각 내부 노드에 자식이 하나만 있는지 확인해야 합니다.

따라서 입력이 preorder =[22, 12, 13, 15, 14]와 같으면 BST가 −

이를 해결하기 위해 하나의 효율적인 접근 방식을 따를 수 있습니다. 노드의 모든 종속 항목이 더 작거나 크므로 다음 단계를 수행할 수 있습니다. -

• 노드의 다음 선주문 후계자 가져오기

• 노드의 마지막 선주문 후계자 가져오기

• 이제 두 계승자가 현재 노드보다 작거나 크면 다시 확인하고 그렇지 않으면 false를 반환합니다.

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

• 다음 :=0, 마지막 :=0
• 0에서 선주문 크기 - 1 사이의 i에 대해
  • 다음 :=선주문[i] - 선주문[i+1]
  • last :=preorder[i] - preorder의 마지막 값
  • 다음 * 마지막 <0이면
    • 거짓을 반환
• 참 반환

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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