如何利用先序和中序创建二叉树 Python

### 使用先序遍历和中序遍历来构建二叉树 为了通过给定的先序遍历(preorder)和中序遍历(inorder)来重建一棵唯一的二叉树，在Python中的实现可以遵循特定的方法[^1]。 #### 构建逻辑解析 在先序遍历列表中，首个元素总是根节点。利用这个特性可以在中序遍历序列里找到对应的分界点，从而区分左子树与右子树部分。对于每一个识别出来的子树范围，重复上述过程直到完成整棵树的恢复工作。 #### Python 实现代码 下面展示了一个具体的Python函数`buildTree`用于根据先序遍历preorder以及中序遍历inorder数组重构原始二叉树结构： ```python # Definition for a binary tree node. 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_index_in_inorder = inorder.index(root_val) root = TreeNode(root_val) # Recursively building the left subtree using corresponding slices of lists root.left = buildTree(preorder[1 : 1 + root_index_in_inorder], inorder[:root_index_in_inorder]) # Similarly recursively constructing the right subtree with appropriate list segments root.right = buildTree(preorder[root_index_in_inorder + 1:], inorder[root_index_in_inorder + 1:]) return root ``` 此算法的时间复杂度主要取决于寻找当前根节点位置的操作次数，最坏情况下可能达到O(n²)，其中n代表节点总数；而空间消耗则主要用于存储递归调用栈帧信息及最终返回的结果对象TreeNode实例化所需内存开销[^2]。