C语言给出后序遍历和中序遍历，求出中序遍历

可以使用递归的方法来求解中序遍历。具体步骤是：先找到后序遍历的最后一个节点作为根节点，然后在中序遍历中找到根节点的位置，将中序遍历分成左子树和右子树两部分，再分别对左右子树进行递归，直到叶子节点为止。最终得到的序列就是中序遍历序列。

相关问题

C语言给出后序遍历和中序遍历，求出中序遍历代码

可以使用递归的方法来求解中序遍历代码。具体步骤如下：

1. 根据后序遍历序列的最后一个元素确定根节点。
2. 在中序遍历序列中找到根节点的位置，将中序遍历序列分成左右两个子序列。
3. 对左子树和右子树分别递归进行步骤1和步骤2，直到序列为空。
4. 将每个节点的值输出，即为中序遍历代码。

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

#include <stdio.h>
#include <stdlib.h>

int search(int arr[], int start, int end, int value) {
    int i;
    for (i = start; i <= end; i++) {
        if (arr[i] == value) {
            return i;
        }
    }
    return -1;
}

void postToIn(int post[], int in[], int start, int end, int *index) {
    if (start > end) {
        return;
    }
    int root = post[*index];
    (*index)--;
    int i = search(in, start, end, root);
    postToIn(post, in, i + 1, end, index);
    printf("%d ", root);
    postToIn(post, in, start, i - 1, index);
}

int main() {
    int post[] = {4, 5, 2, 6, 3, 1};
    int in[] = {4, 2, 5, 1, 3, 6};
    int n = sizeof(post) / sizeof(post[0]);
    int index = n - 1;
    postToIn(post, in, 0, n - 1, &index);
    return 0;
}

输出结果为：4 2 5 1 3 6。

C语言给出后序遍历和中序遍历，求出层序遍历代码

我可以回答这个问题。首先，我们需要了解什么是后序遍历和中序遍历。后序遍历是指先遍历左子树，再遍历右子树，最后遍历根节点。中序遍历是指先遍历左子树，再遍历根节点，最后遍历右子树。层序遍历是指按照树的层次顺序遍历每个节点。

我们可以通过后序遍历和中序遍历构建出二叉树，然后再进行层序遍历。具体的步骤如下：

1. 根据后序遍历找到根节点，然后在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树两部分。

2. 根据左子树和右子树的节点数，将后序遍历也分为左子树和右子树两部分。

3. 递归地构建左子树和右子树，直到叶子节点。

4. 层序遍历二叉树，输出每个节点的值。

下面是代码实现：

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    if (inorder.empty() || postorder.empty()) {
        return NULL;
    }
    int rootVal = postorder.back();
    TreeNode* root = new TreeNode(rootVal);
    int rootIndex = 0;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == rootVal) {
            rootIndex = i;
            break;
        }
    }
    vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
    vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
    vector<int> leftPostorder(postorder.begin(), postorder.begin() + rootIndex);
    vector<int> rightPostorder(postorder.begin() + rootIndex, postorder.end() - 1);
    root->left = buildTree(leftInorder, leftPostorder);
    root->right = buildTree(rightInorder, rightPostorder);
    return root;
}

void levelOrder(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front();
            q.pop();
            cout << node->val << " ";
            if (node->left != NULL) {
                q.push(node->left);
            }
            if (node->right != NULL) {
                q.push(node->right);
            }
        }
    }
}

int main() {
    vector<int> inorder = {4, 2, 5, 1, 6, 3};
    vector<int> postorder = {4, 5, 2, 6, 3, 1};
    TreeNode* root = buildTree(inorder, postorder);
    levelOrder(root);
    return 0;
}

这段代码可以输出二叉树的层序遍历结果。