Python 中從先序遍歷構造二叉搜尋樹

假設我們必須建立一個與給定先序遍歷匹配的二叉搜尋樹。因此，如果先序遍歷類似於 [8,5,1,7,10,12]，則輸出將為 [8,5,10,1,7,null,12]，因此樹將為 -

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

• root := 先序遍歷列表的第 0 個節點
• stack := 一個棧，並將根節點壓入棧中
• 對於先序列表的第二個元素開始的每個元素 i
  • i := 一個值為 i 的節點
  • 如果 i 的值 < 棧頂元素的值，則
    • 棧頂節點的左子節點 := i
    • 將 i 插入到棧中
  • 否則
    • 當棧不為空，且棧頂元素的值 < i 的值時
      • last := 棧頂
      • 從棧中彈出元素
    • 最後一個節點的右子節點 := i
    • 將 i 插入到棧中
• 返回根節點

讓我們看看以下實現以更好地理解 -

示例

class Solution(object):
   def bstFromPreorder(self, preorder):
      """
      :type preorder: List[int]
      :rtype: TreeNode
      """
      root = TreeNode(preorder[0])
      stack = [root]
      for i in preorder[1:]:
         i = TreeNode(i)
         if i.val<stack[-1].val:
            stack[-1].left = i
            stack.append(i)
         else:
            while stack and stack[-1].val<i.val:
               last = stack.pop(-1)
            last.right = i
            stack.append(i)
      return root

輸入

[8,5,1,7,10,12]

輸出

[8,5,10,1,7,null,12]

Arnab Chakraborty

更新於: 2020年5月2日

686 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習