用 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,

更新时间： 2020-11-26

166 次浏览

开启你的 职业生涯

通过完成课程获得认证

立刻开始
广告