如何从preorder和inorder遍历构建二叉树

从preorder和inorder遍历构建二叉树是一个常见的编程问题。以下是一个使用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_index = inorder.index(root_val)
    left_inorder = inorder[:root_index]
    right_inorder = inorder[root_index+1:]
    left_preorder = preorder[1:1+len(left_inorder)]
    right_preorder = preorder[1+len(left_inorder):]
    left_tree = buildTree(left_preorder, left_inorder)
    right_tree = buildTree(right_preorder, right_inorder)
    return TreeNode(root_val, left_tree, right_tree)

这个解决方案首先定义了一个TreeNode类，用于表示二叉树的节点。然后，定义了一个buildTree函数，该函数接受两个列表作为参数：preorder和inorder。preorder列表表示前序遍历，inorder列表表示中序遍历。

函数首先检查preorder和inorder列表是否为空，如果为空，则返回None。接下来，根据preorder列表的第一个元素（即根节点的值）找到inorder列表中的根节点位置。然后，将inorder列表分为左子树和右子树的列表，以及preorder列表分为左子树和右子树的前序遍历列表。

接下来，递归地调用buildTree函数，分别使用左子树的前序遍历和中序遍历列表以及右子树的前序遍历和中序遍历列表来构建左子树和右子树。最后，返回一个新的TreeNode实例，其中包含根节点的值、左子树和右子树。

这个解决方案的时间复杂度为O(n)，其中n是二叉树中节点的数量。