用 Python 從中序和後序遍歷構造二叉樹

假設我們具有二叉樹的中序和後序遍歷序列。我們必須根據這些序列生成樹。所以如果後序和中序序列分別為：[9,15,7,20,3] 和 [9,3,15,20,7]，那麼樹將為 −

讓我們瞭解各步驟 −

  • 假定該方法以先序和中序列表作為 buildTree 引數
  • 根 := 後序列表中的最後一個結點，並從後序列表中刪除第一個結點
  • 根_索引 := 根值在中序列表中的索引
  • 左子樹或根 := buildTree(中序列表中索引從根索引 + 1 到尾部的子集，後序列表)
  • 右子樹或根 := buildTree(中序列表中索引從 0 到根索引的子集，後序列表)

讓我們瞭解以下實現，以便更好地理解 −

示例

 即時演示

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

輸入

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

輸出

9, 15, 7, 20, 3,

更新於:2020-05-04

187 次瀏覽

開啟你的職業生涯

透過學習課程來獲取證書

開始
廣告