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

pythonserver side programmingprogramming更新于 2025/11/22 18:52:17

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

让我们看看步骤 -

假设该方法称为 buildTree，带有前序和中序列表
root := 后序中的最后一个节点，并从后序中删除第一个节点
root_index := 中序列表中 root.val 的索引
left 或 root := buildTree(从 root_index + 1 到末尾的中序子集，后序)
right or root := buildTree(从索引 0 到 root_index 的中序子集，后序)

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

示例

class TreeNode:
   def __init__(self, data, left = None, right = None):
      self.data = data
      self.left = left
      self.right = right
def print_tree(root):
   #print 使用中序遍历
   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([9,3,15,20,7], [9,15,7,20,3]))