用 Python 從給定的後序遍歷構造二叉搜尋樹

假設我們有二叉搜尋樹的後序遍歷序列。我們必須從這些序列生成樹。因此，如果後序序列為 [9,15,7,20,3]，則樹將為 -

要形成一棵樹，我們還需要中序遍歷，但是對於二叉搜尋樹，中序遍歷將按排序形式排列。

讓我們看看步驟 -

  • 中序 = 後序遍歷的排序列表。

  • 定義一個方法 build_tree()，它將接收中序和後序 -

  • 如果中序列表不為空 -

    • 根 := 使用後序的最後一個值建立一個樹節點，然後刪除該元素

    • ind := 根資料在中序列表中的索引

    • 根的右子樹 := build_tree(從索引 ind 到結束的中序，後序)

    • 根的左子樹 := build_tree(從 0 到索引 ind - 1 的中序，後序)

  • 返回根

示例

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

即時演示

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   if root is not None:
      print_tree(root.left)
      print(root.data, end = ', ')
      print_tree(root.right)
class Solution(object):
   def buildTree(self, inorder, postorder):
      if inorder:
         root = TreeNode(postorder.pop())
         ind = inorder.index(root.data)
         root.right = self.buildTree(inorder[ind+1:],postorder)
         root.left = self.buildTree(inorder[:ind],postorder)
         return root
ob1 = Solution()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))

輸入

[9,3,15,20,7]
[9,15,7,20,3]

輸出

[3,7,9,15,20]

更新於: 2020-08-27

207 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告