在 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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

