python 前序遍历和中序遍历还原数组

### 构建二叉树的过程 要根据前序遍历和中序遍历的结果重建一棵二叉树，可以按照以下逻辑实现： #### 原理说明 1. **前序遍历的特点**：前序遍历的第一个节点总是当前子树的根节点[^2]。 2. **中序遍历的作用**：利用中序遍历可以找到该根节点对应的左右子树范围。因为中序遍历会依次访问左子树、根节点和右子树[^1]。 基于上述特性，可以通过递归的方式逐步构建整个二叉树。 --- #### Python 实现代码 以下是完整的 Python 代码用于根据前序遍历和中序遍历序列重建二叉树： ```python # 定义二叉树节点类 class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def buildTree(preorder, inorder): if not preorder or not inorder: return None # 当前子树的根节点值为前序遍历的第一个元素 root_val = preorder[0] root = TreeNode(root_val) # 查找根节点在中序遍历中的索引位置 index_in_inorder = inorder.index(root_val) # 划分左右子树的前序和中序遍历部分 left_inorder = inorder[:index_in_inorder] right_inorder = inorder[index_in_inorder + 1:] left_preorder = preorder[1:len(left_inorder) + 1] right_preorder = preorder[len(left_inorder) + 1:] # 递归构造左右子树 root.left = buildTree(left_preorder, left_inorder) root.right = buildTree(right_preorder, right_inorder)[^1] return root ``` --- #### 测试用例 假设我们有如下输入数据： - `preorder` = `[3,9,20,15,7]` - `inorder` = `[9,3,15,20,7]` 调用函数并打印结果： ```python # 创建测试用例 preorder = [3, 9, 20, 15, 7] inorder = [9, 3, 15, 20, 7] # 调用函数 root = buildTree(preorder, inorder) # 辅助函数：按层序遍历输出二叉树结构 from collections import deque def levelOrder(root): result = [] queue = deque([root]) while queue: node = queue.popleft() if node: result.append(node.val) queue.append(node.left) queue.append(node.right) else: result.append(None) return result print(levelOrder(root)) # 输出应为 [3, 9, 20, None, None, 15, 7] ``` 运行以上代码后，得到的二叉树层次遍历结果为 `[3, 9, 20, None, None, 15, 7]`，验证了算法的有效性。 --- ### 注意事项 1. 如果输入的前序或中序遍历列表为空，则返回 `None` 表示空树[^4]。 2. 输入的前序和中序遍历必须对应于同一棵二叉树，否则无法正确重构[^5]。 ---