由树的先序遍历序列和中序遍历序列创建一棵二叉树。

根据给定的先序遍历序列和中序遍历序列，可以通过递归的方式创建一棵二叉树。具体步骤如下：
1. 根据先序遍历序列，确定根节点，创建一个根节点。
2. 在中序遍历序列中找到根节点的位置，根节点左边的部分为左子树的中序遍历序列，右边的部分为右子树的中序遍历序列。
3. 根据左子树的中序遍历序列和左子树的先序遍历序列，递归创建左子树。
4. 根据右子树的中序遍历序列和右子树的先序遍历序列，递归创建右子树。
5. 将左子树和右子树分别作为根节点的左右子树。

下面是Python代码实现：

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if not preorder:
            return None
        root = TreeNode(preorder[0])
        mid_idx = inorder.index(preorder[0])
        root.left = self.buildTree(preorder[1:mid_idx+1], inorder[:mid_idx])
        root.right = self.buildTree(preorder[mid_idx+1:], inorder[mid_idx+1:])
        return root

相关问题

C++根据二叉树的先序遍历序列和中序遍历序列，求其后序遍历序列

我们可以利用递归的思想来解决这个问题。一个二叉树的先序遍历序列的第一个元素一定是根节点，而在中序遍历序列中，根节点的左侧都是左子树的节点，右侧都是右子树的节点。因此，我们可以根据这个性质来构建二叉树，并且递归地处理左右子树。

具体的实现步骤如下：

1. 根据先序遍历序列的第一个元素创建根节点。
2. 在中序遍历序列中找到根节点的位置，将序列分成左右两部分。
3. 递归地处理左子树，将左子树的先序遍历序列和中序遍历序列作为参数传入。
4. 递归地处理右子树，将右子树的先序遍历序列和中序遍历序列作为参数传入。
5. 将根节点的值加入到后序遍历序列中。
6. 返回后序遍历序列。

下面是 C++ 的代码实现：

#include <vector>
#include <unordered_map>

using namespace std;

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

class Solution {
public:
    vector<int> buildTree(vector<int>& preorder, vector<int>& inorder) {
        // 将中序遍历序列的每个元素及其下标存储到哈希表中
        for (int i = 0; i < inorder.size(); i++) {
            index[inorder[i]] = i;
        }
        return buildTree(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }

private:
    unordered_map<int, int> index;

    // 根据先序遍历序列和中序遍历序列构建二叉树，并返回后序遍历序列
    vector<int> buildTree(vector<int>& preorder, int preStart, int preEnd,
                          vector<int>& inorder, int inStart, int inEnd) {
        if (preStart > preEnd) {
            return {};
        }
        // 先序遍历序列的第一个元素是根节点
        int rootVal = preorder[preStart];
        TreeNode* root = new TreeNode(rootVal);
        // 在中序遍历序列中找到根节点的位置
        int rootIndex = index[rootVal];
        // 计算左子树的长度
        int leftSize = rootIndex - inStart;
        // 递归处理左子树
        vector<int> left = buildTree(preorder, preStart + 1, preStart + leftSize,
                                     inorder, inStart, rootIndex - 1);
        // 递归处理右子树
        vector<int> right = buildTree(preorder, preStart + leftSize + 1, preEnd,
                                      inorder, rootIndex + 1, inEnd);
        // 将根节点的值加入到后序遍历序列中
        vector<int> res = left;
        res.insert(res.end(), right.begin(), right.end());
        res.push_back(rootVal);
        return res;
    }
};

时间复杂度为 O(n)，其中 n 是二叉树中的节点个数。这是因为我们需要遍历每个节点恰好一次。空间复杂度为 O(n)，其中 n 是二叉树中的节点个数。除了存储答案所需的空间，我们还需要 O(n) 的空间存储哈希表。

下面是给定一棵二叉树的先序遍历序列和中序遍历序列，输出后序遍历序列的c语言代码

以下是二叉树后序遍历的 C 语言代码实现：

#include <stdio.h>  
#include <stdlib.h>  
  
typedef struct Node  
{  
    char data;  
    struct Node *left;  
    struct Node *right;  
}Node, *pNode;  
  
Node *createTree(char *preorder, char *inorder, int length)  
{  
    if(preorder == NULL || inorder == NULL || length <= 0)  
        return NULL;  
  
    Node *root = (Node*)malloc(sizeof(Node));  
    root->data = *preorder;  
  
    int rootIndex = 0;  
    while(rootIndex < length && *(inorder + rootIndex) != *preorder)  
        ++rootIndex;  
  
    if(rootIndex >= length)  
        return NULL;  
  
    root->left = createTree(preorder + 1, inorder, rootIndex);  
    root->right = createTree(preorder + rootIndex + 1, inorder + rootIndex + 1, length - rootIndex - 1);  
  
    return root;  
}  
  
void postorderTraversal(Node *root)  
{  
    if(root == NULL)  
        return;  
  
    postorderTraversal(root->left);  
    postorderTraversal(root->right);  
    printf("%c ", root->data);  
}  
  
int main()  
{  
    char preorder[] = "ABDECFG";  
    char inorder[] = "DBEAFCG";  
    int length = sizeof(preorder) / sizeof(char);  
  
    Node *root = createTree(preorder, inorder, length);  
    printf("The postorder traversal of the binary tree is: ");  
    postorderTraversal(root);  
  
    return 0;  
}  

其中，createTree 函数用于根据给定的先序遍历序列和中序遍历序列构建二叉树，postorderTraversal 函数用于输出后序遍历序列。需要注意的是，以上代码中的二叉树假定没有重复的节点。