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

Arnab Chakraborty

更新于: 2020-08-27

207 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习