给定一颗二叉树先序遍历的输出结果，求出该树的中序遍历的输出结果

这道题可以用递归的方式解决。先序遍历可以得到二叉树的根节点，而中序遍历可以将二叉树分成左右两个子树。因此，可以递归地对左右子树求解，并将结果合并起来，即可得到整棵二叉树的中序遍历结果。

具体的算法如下：

1. 如果先序遍历结果为空，则返回空列表。

2. 获取先序遍历结果的第一个元素，即为根节点。

3. 在中序遍历结果中找到根节点的位置，将其分成左右两个子树。

4. 递归地对左子树和右子树求解，将结果合并起来即可得到整棵二叉树的中序遍历结果。

代码如下所示：

def inorder(preorder, inorder):
    if not preorder:
        return []
    root = preorder[0]
    idx = inorder.index(root)
    left = inorder[:idx]
    right = inorder[idx+1:]
    return inorder(left, preorder[1:len(left)+1]) + [root] + inorder(right, preorder[len(left)+1:])

这里假设输入的先序遍历和中序遍历结果已经被转化为了列表形式。

相关问题

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):
    if not preorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    i = 1
    while i < len(preorder) and preorder[i] < root_val:
        i += 1
    root.left = buildTree(preorder[1:i])
    root.right = buildTree(preorder[i:])
    return root

def inorderTraversal(root):
    if not root:
        return []
    return inorderTraversal(root.left) + [root.val] + inorderTraversal(root.right)

preorder = [5, 3, 1, 4, 7, 6, 8]
root = buildTree(preorder)
inorder = inorderTraversal(root)
print(inorder) #[1, 3, 4, 5, 6, 7, 8]

该代码通过 buildTree 函数构建出了给定的二叉树，并通过 inorderTraversal 函数遍历输出了中序遍历的结果。

c语言实现，给定一颗二叉树先序遍历的输出结果，求出该树的中序遍历的

输出结果。

这道题可以通过递归实现。我们可以先找到根节点，然后根据根节点的位置，将先序遍历序列分成左子树和右子树两个部分。再利用递归的方式求出左子树和右子树的中序遍历序列，最后将它们拼接起来，就得到了整棵二叉树的中序遍历序列。

具体实现可以参考下面的代码：

#include <stdio.h>
#include <string.h>

void find_inorder(char* preorder, char* inorder, int len, char* result) {
    if (len <= 0) return;

    int root_pos = strchr(inorder, *preorder) - inorder;
    find_inorder(preorder+1, inorder, root_pos, result);
    result[root_pos] = *preorder;
    find_inorder(preorder+1+root_pos, inorder+root_pos+1, len-1-root_pos, result);
}

int main() {
    char preorder[] = "GDAFEMHZ";
    char inorder[] = "ADEFGHMZ";
    int len = strlen(preorder);
    char result[len+1];

    find_inorder(preorder, inorder, len, result);
    result[len] = '\0';

    printf("%s\n", result);

    return 0;
}

输出结果为：ADEFGHMZ。