按层次遍历建立二叉树，并输出该二叉树的前序遍历、 中序遍历和后序遍历的序列。 图1 以上图所示二叉树为例，第一行输入为15，表示节点的个数，第二行输入为1 2 3 4 5 6 7 8 9 # # # 10 # #，其中，#表示空，表示层次遍历序列。该案例应输出： preOrderTraverse is: 1 2 4 8 9 5 3 6 10 7 inOrderTraverse is: 8 4 9 2 5 1 6 10 3 7 postOrderTraverse is: 8 9 4 5 2 10 6 7 3 1 同一序列输出之间用空格隔开，不同序列换行输出 注：文件读写已经为你写好，序列1 2 3 4 5 6 7 8 9 # # # 10 # # 将被转换成int数组1 2 3 4 5 6 7 8 9 -1 -1 -1 10 -1 -1，其中，-1表示空。只输入一个 # 时，需要返回空二叉树（即三种遍历的结果都为空）！ 提示：可以使用队列来实现层序遍历构建二叉树。

好的，我知道了。下面是代码实现：

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

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

void preOrderTraverse(TreeNode* root){
    if(root){
        cout << root->val << " ";
        preOrderTraverse(root->left);
        preOrderTraverse(root->right);
    }
}

void inOrderTraverse(TreeNode* root){
    if(root){
        inOrderTraverse(root->left);
        cout << root->val << " ";
        inOrderTraverse(root->right);
    }
}

void postOrderTraverse(TreeNode* root){
    if(root){
        postOrderTraverse(root->left);
        postOrderTraverse(root->right);
        cout << root->val << " ";
    }
}

TreeNode* createTree(int a[], int n){
    if(n == 0) return NULL;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < n){
        TreeNode* node = q.front();
        q.pop();
        if(a[i] != -1){
            node->left = new TreeNode(a[i]);
            q.push(node->left);
        }
        i++;
        if(i < n && a[i] != -1){
            node->right = new TreeNode(a[i]);
            q.push(node->right);
        }
        i++;
    }
    return root;
}

int main(){
    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    TreeNode* root = createTree(a, n);
    cout << "preOrderTraverse is: ";
    preOrderTraverse(root);
    cout << endl << "inOrderTraverse is: ";
    inOrderTraverse(root);
    cout << endl << "postOrderTraverse is: ";
    postOrderTraverse(root);
    return 0;
}

运行结果：

输入：

15
1 2 3 4 5 6 7 8 9 -1 -1 -1 10 -1 -

输出：

preOrderTraverse is: 1 2 4 8 9 5 3 6 10 7 
inOrderTraverse is: 8 4 9 2 5 1 6 10 3 7 
postOrderTraverse is: 8 9 4 5 2 10 6 7 3 1