与えられた二分木の垂直レベルがPythonでソートされているかどうかを確認します

したがって、入力がl =-1

レベル-1の要素は3.7であり、ソートされているため、出力はTrueになります。

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

• ルートがnullの場合、

  • Trueを返す

• previous_value：=-inf

• current_level：=0

• current_node：=値が0の新しいツリーノード

• qという名前の1つのデキューを定義します

• qの最後に（root、0）を挿入します

• qが空でない間、実行します

  • current_node：=q [0、0]

  • current_level：=q [0、1]

  • qの左側から要素を削除

  • current_levelがlevelと同じ場合、

    • previous_value <=current_node.valの場合、

      • previous_value：=current_node.val

    • それ以外の場合

      • Falseを返す

  • current_node.leftがnullでない場合、

    • qの最後に（current_node.left、current_level-1）を挿入します

  • current_node.rightがnull以外の場合、

    • qの最後に（current_node.right、current_level + 1）を挿入します

• Trueを返す

例

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

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