在 Python 中从后序遍历和中序遍历构建二叉树

假设我们有二叉树的中序遍历和后序遍历序列。我们需要从这些序列中生成一棵树。因此，如果后序遍历和中序遍历序列是 [9,15,7,20,3] 和 [9,3,15,20,7]，则这棵树将为：

让我们看看步骤：

• 定义一个方法 build_tree()，它将使用中序、后序：

• 如果中序列表不为空：

  • root := 创建一个树节点，其值为后序的最后一个值，然后删除该元素

  • ind := 在中序列表中找到 root 数据的索引

  • root 的右节点 := build_tree(从索引 ind 到末尾的中序、后序)

  • root 的左节点 := build_tree(从 0 到索引 ind - 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, 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()
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,3,15,20,7]

Arnab Chakraborty

更新于：2020 年 8 月 27 日

539 次浏览

开启你的 职业生涯

完成课程即可获得认证

开始学习