Python程式：查詢二叉樹中次深節點

假設我們有一個二叉樹；我們需要找到次深葉節點的深度。如果有多個最深葉節點，則次深葉節點將是次高的節點。我們知道根節點的深度為0。

因此，如果輸入如下所示：

則輸出將為1，因為次深節點為3。

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

  • 如果根節點為空，則
    • 返回空
  • 節點 := 一個新的列表
  • 將根節點插入節點列表的末尾
  • 計數 := 0，前 := 0，現 := 0
  • 當節點列表不為空時，執行以下操作：
    • 新建 := 一個新的列表
    • 標誌 := True
    • 對於節點列表中的每個節點，執行以下操作：
      • 如果標誌為真且（節點的左子節點為空）且（節點的右子節點為空），則
        • 前 := 現
        • 現 := 計數
        • 標誌 := False
      • 如果節點的左子節點不為空，則
        • 將節點的左子節點插入新建列表的末尾
      • 如果節點的右子節點不為空，則
        • 將節點的右子節點插入新建列表的末尾
    • 節點 := 新建
    • 計數 := 計數 + 1
  • 返回前

讓我們看看下面的實現來更好地理解

示例

線上演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right

class Solution:
   def solve(self, root):
      if root is None:
         return None
      nodes = []
      nodes.append(root)
      count = 0
      prev = 0
      now = 0
      while nodes:
         new = []
         flag = True
         for node in nodes:
         if flag and (not node.left) and (not node.right):
            prev = now
            now = count
            flag = False
         if node.left:
            new.append(node.left)
         if node.right:
            new.append(node.right)
      nodes = new
      count += 1
   return prev

ob = Solution()
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)
root.right.right.right = TreeNode(8)
print(ob.solve(root))

輸入

root = TreeNode(2)
root.left = TreeNode(3)

root.right = TreeNode(4)
root.right.left = TreeNode(5)
root.right.right = TreeNode(6)
root.right.left.left = TreeNode(7)

root.right.right.right = TreeNode(8)

輸出

1

更新於：2020年11月26日

258 次瀏覽

啟動您的職業生涯

完成課程獲得認證

開始學習
廣告