使用 Python 中的 Stack 根据给定的后序遍历构造 BST

pythonserver side programmingprogramming更新于 2025/10/17 10:20:17

假设我们有一个二叉搜索树的后序遍历；我们必须从中找到二叉搜索树。

因此，如果输入为 [6, 12, 10, 55, 45, 15]，则输出将

为了解决这个问题，我们将遵循以下步骤 −

定义一个函数solve()。这将采用后序
n := 后序的大小
root := 使用后序的最后一个元素创建一个新的树节点
stk := 一个堆栈
将根插入 stk
i := n - 2
当 i >= 0 时，执行
- x := 使用值 postorder[i] 创建一个新节点
- 当 stk 不为空且 postorder[i] < stk 顶部的值，执行
  - temp := stk 顶部
  - 从 stk 中删除顶部元素
- 如果 temp 不为空，则
  - temp.left := x
- 否则，
  - stk 顶部元素的右侧 := x
- 将 x 插入 stk
- i := i - 1
返回根
从主方法执行以下操作−
返回 resolve(postorder)

示例

让我们看看下面的实现以便更好地理解 −

class TreeNode:
   def __init__(self, data = 0):
      self.val = data
      self.left = None
      self.right = None
def solve(postorder):
   n = len(postorder)
   root = TreeNode(postorder[n - 1])
   stk = []
   stk.append(root)
   i = n - 2
   while ( i >= 0):
      x = TreeNode(postorder[i])
      temp = None
      while (len(stk) > 0 and postorder[i] < stk[-1].val) :
         temp = stk[-1]
         stk.pop()
      if (temp != None):
         temp.left = x
      else:
         stk[-1].right = x
      stk.append(x)
      i = i - 1
   return root
def build_tree(postorder):
   return solve(postorder)
def inord( node):
   if node:
      inord(node.left)
      print( node.val, end = " ")
      inord(node.right)
postorder = [6, 12, 10, 55, 45, 15]
root = build_tree(postorder)
print( "Inorder traversal:", end = " ")
inord(root)