给定一棵满二叉树先序遍历的结果求该树中序遍历的输出结果代码怎么写优化时间复杂度最低

由于这是一棵满二叉树，因此我们可以通过先序遍历的结果确定根节点，然后递归地构建左右子树。

具体来说，假设先序遍历结果为 preOrder，我们可以取出 preOrder 的第一个元素作为根节点，然后再将 preOrder 分成左右两个子序列，分别递归地对左右子树进行构建。对于左子树的先序遍历序列，我们可以通过 preOrder[1:] 的前一半来获取；对于右子树的先序遍历序列，我们可以通过 preOrder[1:] 的后一半来获取。而中序遍历的结果可以通过递归地对左右子树进行求解，再在根节点的值之前输出左子树的中序遍历结果，根节点的值，之后输出右子树的中序遍历结果。

代码如下：

def inorder(preOrder):
    if not preOrder:
        return []
    root = preOrder[0]
    n = len(preOrder)
    i = 1
    while i < n and preOrder[i] < root:
        i += 1
    left = inorder(preOrder[1:i])
    right = inorder(preOrder[i:])
    return left + [root] + right

时间复杂度为 O(nlogn)，其中 n 是二叉树的节点数。这是因为对于每个节点，我们需要遍历该节点的左子树和右子树，而左子树和右子树的节点数分别为 n/2。因此总共的遍历次数为 logn 层，每层需要 O(n) 的时间复杂度。