使用 Python 判斷二叉樹的指定垂直層是否已排序

假設我們有一個二叉樹，我們需要檢查二叉樹的給定垂直層是否已排序。當兩個節點重疊時，檢查它們在其所屬層級中是否按排序順序排列。

因此，如果輸入類似於 l = -1

則輸出將為 True，因為 -1 層級的元素為 3、7，它們已排序。

為了解決這個問題，我們將遵循以下步驟：

  • 如果根節點為空，則

    • 返回 True

  • previous_value := -inf

  • current_level := 0

  • current_node := 一個值為 0 的新樹節點

  • 定義一個名為 q 的雙端佇列

  • 將 (root, 0) 插入 q 的末尾

  • 當 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 不為空，則

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

    • 如果 current_node.right 不為空，則

      • 將 (current_node.right, current_level + 1) 插入 q 的末尾

  • 返回 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

更新於: 2020-08-25

53 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始
廣告

© . All rights reserved.