Python中檢查BST的每個內部節點是否只有一個子節點

假設我們有二叉搜尋樹 (BST) 的先序遍歷。我們必須檢查每個內部節點是否只有一個子節點。

因此，如果輸入類似於preorder = [22, 12, 13, 15, 14]，則輸出將為True，因為BST類似於：

為了解決這個問題，我們可以遵循一種有效的方法。由於一個節點的所有後代都小於或大於它，那麼我們可以遵循以下步驟：

• 獲取節點的下一個先序後繼

• 獲取節點的最後一個先序後繼

• 現在，當兩個後繼都小於或大於當前節點時，再次檢查，否則返回false。

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

• next := 0, last := 0
• 對於範圍從0到preorder大小減1的i，執行：
  • next := preorder[i] - preorder[i+1]
  • last := preorder[i] - preorder的最後一個值
  • 如果 next * last < 0，則
    • 返回False
• 返回True

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

示例

線上演示

def solve(preorder):
next = 0
last = 0
for i in range(len(preorder)-1):
next = preorder[i] - preorder[i+1]
last = preorder[i] - preorder[-1]
if next * last < 0:
return False
return True
preorder = [22, 12, 13, 15, 14] print(solve(preorder))

輸入

[22, 12, 13, 15, 14]

輸出

True

Arnab Chakraborty

更新於：2020-12-30

257 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始