二叉树已知前序中序求后序

已知二叉树的前序遍历和中序遍历，可以通过以下步骤来求解后序遍历：
1. 首先，根据前序遍历的顺序，找到根节点。
2. 接下来，在中序遍历中找到根节点的位置，根据根节点的位置将中序遍历划分为左子树和右子树。
3. 根据左子树的节点个数，将前序遍历划分为左子树的前序遍历和右子树的前序遍历。
4. 分别对左子树和右子树递归地执行上述步骤，得到左子树的后序遍历和右子树的后序遍历。
5. 将左子树的后序遍历和右子树的后序遍历拼接在一起，再将根节点添加到末尾，即为所求的后序遍历。

相关问题

c语言二叉树已知前序中序求后序完整代码

以下为 C 语言的二叉树已知前序中序求后序的完整代码：

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

// 定义二叉树节点
typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} TreeNode;

// 递归构建二叉树
TreeNode* buildTree(char *preorder, char *inorder, int preStart, int preEnd, int inStart, int inEnd) {
    if (preStart > preEnd || inStart > inEnd) {
        return NULL;
    }

    // 获取前序遍历的根节点
    TreeNode *root = (TreeNode*) malloc(sizeof(TreeNode));
    root->data = preorder[preStart];
    root->left = NULL;
    root->right = NULL;

    // 找到中序遍历中根节点的位置
    int rootIndex;
    for (int i = inStart; i <= inEnd; i++) {
        if (inorder[i] == preorder[preStart]) {
            rootIndex = i;
            break;
        }
    }

    // 递归构建左子树和右子树
    root->left = buildTree(preorder, inorder, preStart+1, preStart+rootIndex-inStart, inStart, rootIndex-1);
    root->right = buildTree(preorder, inorder, preStart+rootIndex-inStart+1, preEnd, rootIndex+1, inEnd);

    return root;
}

// 后序遍历输出二叉树
void postorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%c", root->data);
}

int main(void) {
    char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
    char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};

    TreeNode *root = buildTree(preorder, inorder, 0, 5, 0, 5);

    printf("后序遍历结果：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

以上代码实现了已知前序遍历和中序遍历构建二叉树，并输出后序遍历的结果。需要注意的是，代码中的前序遍历和中序遍历都是以字符数组的形式给出的，可以根据实际情况进行修改。

二叉树已知前序中序求后序代码详解

二叉树的前序遍历顺序为：根节点、左子树、右子树；中序遍历顺序为：左子树、根节点、右子树。因此，如果已知一个二叉树的前序遍历和中序遍历，就可以推导出该二叉树的后序遍历。

具体实现方法如下：

1. 定义二叉树节点结构体

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

2. 以前序遍历的第一个节点作为根节点，在中序遍历中找到根节点的位置，将中序遍历分为左子树和右子树两部分。

3. 递归构建左子树和右子树，左子树的前序遍历和中序遍历可以分别由原先的前序遍历和左子树部分的中序遍历得到，右子树的前序遍历和中序遍历可以分别由原先的前序遍历和右子树部分的中序遍历得到。

4. 后序遍历的顺序为左子树、右子树、根节点，因此在递归构建完左子树和右子树之后，将当前节点的值加入到结果数组中即可。

完整代码如下：

class Solution {
public:
    vector<int> inorder, preorder, postorder;
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        this->preorder = preorder;
        this->inorder = inorder;
        return build(0, preorder.size() - 1, 0, inorder.size() - 1);
    }

    TreeNode* build(int preLeft, int preRight, int inLeft, int inRight) {
        if (preLeft > preRight) return NULL;

        int rootVal = preorder[preLeft];
        int index = 0;
        for (int i = inLeft; i <= inRight; i++) {
            if (inorder[i] == rootVal) {
                index = i;
                break;
            }
        }

        int leftSize = index - inLeft;
        TreeNode* root = new TreeNode(rootVal);
        root->left = build(preLeft + 1, preLeft + leftSize, inLeft, index - 1);
        root->right = build(preLeft + leftSize + 1, preRight, index + 1, inRight);

        postorder.push_back(rootVal);

        return root;
    }
};