如何通过中序与前序遍历序列构建二叉树？递归实现遇阻求助

问题描述 #

我希望通过给定的中序和前序遍历序列构建二叉树，例如pre = [3,9,1,2,20,15,7]，in = [1,9,2,3,15,30,7]。我知道初始步骤：前序遍历的第一个元素为根节点，将中序遍历序列以根节点为界拆分，左侧为左子树序列，右侧为右子树序列。但我在如何递归处理左右子树这一步遇到了困难。以下是我目前的代码：

class tree: 
    def build(self, pre, in):
        if self._value == None:
            self._value = pre[0]
        left = in[:self._value] 
        right = in[self._value+1:]
        return self 

问题分析 #

你的代码存在几个关键问题：

• 错误地用节点值self._value作为中序序列的切片索引，实际应该找根节点在中序序列中的位置索引
• 完全缺失递归构建左右子树的逻辑，仅处理了根节点就直接返回
• 类的设计不符合二叉树构建的常规模式，缺少独立的节点定义

解决思路 #

递归构建的核心逻辑是：

1. 终止条件：若当前前序/中序序列为空，说明当前子树不存在，返回None
2. 取当前前序序列首元素作为根节点
3. 在中序序列中定位根节点，拆分出左、右子树的中序序列
4. 根据左子树的节点数量，拆分出左、右子树的前序序列
5. 递归构建左、右子树，挂载到当前根节点上

完整实现代码 #

# 定义二叉树节点类
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class TreeBuilder:
    def buildTree(self, preorder, inorder):
        # 递归终止：序列为空则返回空节点
        if not preorder or not inorder:
            return None
        
        # 前序首元素为当前根节点
        root_val = preorder[0]
        root = TreeNode(root_val)
        
        # 找到根节点在中序序列中的索引位置
        root_idx = inorder.index(root_val)
        
        # 拆分左子树的中序、前序序列
        left_in = inorder[:root_idx]
        left_pre = preorder[1 : 1 + len(left_in)]
        
        # 拆分右子树的中序、前序序列
        right_in = inorder[root_idx+1:]
        right_pre = preorder[1 + len(left_in):]
        
        # 递归构建左右子树并挂载
        root.left = self.buildTree(left_pre, left_in)
        root.right = self.buildTree(right_pre, right_in)
        
        return root

代码说明 #

• TreeNode类：标准的二叉树节点结构，包含值、左子节点、右子节点三个属性
• 终止条件：处理空序列的情况，避免递归无限进行
• 根节点定位：用index方法快速找到根节点在中序序列中的位置
• 序列拆分：左子树的前序序列长度与左中序序列长度完全一致，以此为依据拆分前序序列；剩余部分则是右子树的前序序列
• 递归挂载：将递归生成的左右子树分别赋值给当前根节点的对应属性

测试示例 #

用你提供的测试数据验证：

builder = TreeBuilder()
pre = [3,9,1,2,20,15,7]
in_seq = [1,9,2,3,15,30,7]  # 避免使用Python关键字in作为变量名
root = builder.buildTree(pre, in_seq)

执行后即可得到符合预期的二叉树结构。

内容的提问来源于stack exchange，提问作者user20288757