在 Python 中查找二叉树的给定垂直层是否已排序

pythonserver side programmingprogramming更新于 2025/10/10 9:16:17

假设我们有二叉树;我们必须检查二叉树的给定垂直层是否已排序。当两个节点重叠时,检查它们在所属级别中是否按排序顺序排列。

因此,如果输入为 l = -1

则输出将为 True,因为级别 -1 中的元素为 3,7,并且它们已排序。

为了解决这个问题,我们将遵循以下步骤 −

  • 如果 root 为空,则

    • 返回 True

  • previous_value := -inf

  • current_level := 0

  • current_node := 一个值为 0 的新树节点

  • 定义一个名为 q 的出队

  • 在 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 非空,则

      • 在 q 末尾插入 (current_node.left, current_level - 1)

    • 如果 current_node.right 非空,则

      • 在 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

相关文章


有用资源