在 Python 中根据给定的后序构造二叉搜索树

pythonserver side programmingprogramming更新于 2025/10/17 9:16:17

假设我们有一个二叉搜索树的后序遍历序列。我们必须根据这些序列生成树。因此，如果后序序列为 [9,15,7,20,3]，则树将为 −

要形成一棵树，我们也需要中序遍历，但对于二叉搜索树，中序遍历将采用排序形式。

让我们看看步骤 −

中序 = 后序遍历的排序列表。
定义一个方法 build_tree()，它将采用中序、后序 −
如果中序列表不为空−
- root := 创建一个具有 postorder 最后一个值的树节点，然后删除该元素
- ind := 中序列表中根数据的索引
- root 的右侧 := build_tree(inorder 从索引 ind 到末尾，postorder)
- root 的左侧 := build_tree(inorder 从 0 到索引 ind - 1，postorder)
返回 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()
postorder = [3,9,20,15,7]
inorder = list(sorted([3,9,20,15,7]))
print_tree(ob1.buildTree(inorder, postorder))