用 python 生成樹的先序和中序遍歷程式

假設我們已經有了二叉樹的先序和中序遍歷。我們需要從這些序列中恢復整棵樹。所以如果先序和中序序列分別是 [3,9,20,15,7] 和 [9,3,15,20,7]，那這棵樹將是：

我們來看一下具體步驟：

• 定義名為 buildTree() 的方法，這個方法將先序和中序遍歷序列作為引數。
• 如果中序遍歷列表不為空，則：
  • root := 建立一個樹節點，其值為先序序列中第一個元素，並從先序遍歷中移除第一個元素。
  • root_index := root 的值在中序列表中的索引。
  • root 的左節點 := buildTree(preorder, inorder[從索引 0 到 root_index])。
  • root 的右節點 := buildTree(preorder, inorder[從索引 root_index+1 到末尾])。
• return root。

讓我們來看一下以下實現來加深理解：

範例

線上演示

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, 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([3,9,20,15,7], [9,3,15,20,7]))

輸入

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

輸出

9,3,15,20,7,

Arnab Chakraborty

更新時間： 2020-11-26

166 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立刻開始