주어진 수직 레벨의 이진 트리가 Python에서 정렬되었는지 여부 찾기

바이너리 트리가 있다고 가정합니다. 주어진 이진 트리의 수직 레벨이 정렬되었는지 여부를 확인해야 합니다. 두 개의 노드가 겹칠 경우 해당 노드가 속한 레벨의 순서대로 정렬되었는지 확인합니다.

따라서 입력이 l =-1

레벨 -1의 요소가 3,7이고 정렬되므로 출력은 True가 됩니다.

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

• 루트가 null이면

  • 참을 반환

• 이전 값 :=-inf

• current_level :=0

• current_node :=값이 0인 새 트리 노드

• q

  라는 이름의 대기열 하나를 정의합니다.

• q의 끝에 (루트, 0) 삽입

• q가 비어 있지 않은 동안 수행

  • 현재 노드 :=q[0, 0]

  • 현재_레벨 :=q[0, 1]

  • q의 왼쪽에서 요소 삭제

  • current_level이 level과 같으면

    • 이전 값 <=current_node.val이면

      • 이전 값 :=current_node.val

    • 그렇지 않으면

      • 거짓을 반환

  • current_node.left가 null이 아니면

    • q의 끝에 (current_node.left, current_level - 1) 삽입

  • current_node.right가 null이 아니면

    • q의 끝에 (current_node.right, current_level + 1) 삽입

• 참을 반환

예시

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

from collections import deque
from sys import maxsize
INT_MIN = -maxsize
class TreeNode:
   def __init__(self, key):
      self.val = key
      self.left = None
      self.right = None
def are_elements_sorted(root, level):
   if root is None:
      return True
   previous_value = INT_MIN
   current_level = 0
   current_node = TreeNode(0)
   q = deque()
   q.append((root, 0))
   while q:
      current_node = q[0][0]
      current_level = q[0][1]
      q.popleft()
      if current_level == level:
         if previous_value <= current_node.val:
            previous_value = current_node.val
         else:
            return False
      if current_node.left:
         q.append((current_node.left, current_level - 1))
      if current_node.right:
         q.append((current_node.right, current_level + 1))
   return True
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(6)
root.left.left = TreeNode(8)
root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)
level = -1
print(are_elements_sorted(root, level))

입력

root = TreeNode(2) root.left = TreeNode(3) root.right = TreeNode(6)
root.left.left = TreeNode(8) root.left.right = TreeNode(5)
root.left.right.left = TreeNode(7)

출력

True