已知二叉树的先序序列 输出层序遍历序列用C++写出程序

在C++中，如果你想要将给定的二叉树的先序遍历序列转换成层序遍历序列，可以使用队列数据结构来辅助。这里是一个简单的步骤描述：

1. 先序遍历首先访问根节点，然后递归地处理左子树和右子树。所以，对于先序序列中的每个元素，它代表当前节点。

2. 当访问到一个节点时，将其添加到队列中。同时，初始化一个空的结果数组或向量用于存储层序序列。

3. 遍历过程中，从队列中取出节点，并将它的值加入结果。然后将该节点的左右子节点（如果存在）分别入队。

4. 继续上述过程，直到队列为空。

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

#include <iostream>
#include <vector>
#include <queue>

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

std::vector<int> levelOrderPreorderTraversal(std::vector<int>& preorder) {
    if (preorder.empty()) return {};

    std::vector<int> result; // 存储层序遍历结果
    std::queue<TreeNode*> q; // 使用队列存储待访问的节点

    TreeNode* root = nullptr;
    for (int num : preorder) {
        // 先序遍历的第一个元素是根节点
        if (!root) {
            root = new TreeNode(num);
            q.push(root);
        } else {
            // 根据先序遍历，后续元素为左子节点或右子节点
            TreeNode* node = q.front();
            q.pop();

            if (num < node->val) { // 如果是左子节点
                node->left = new TreeNode(num);
                q.push(node->left);
            } else { // 右子节点
                node->right = new TreeNode(num);
                q.push(node->right);
            }
        }

        // 将当前节点添加到结果中，因为已经处理完了其子节点
        if (node && node->left == nullptr && node->right == nullptr) {
            result.push_back(node->val);
            delete node;
        }
    }

    return result;
}

int main() {
    std::vector<int> preorder = {1, 2, 4, 5, 3, 6};
    std::vector<int> layerOrder = levelOrderPreorderTraversal(preorder);

    for (int num : layerOrder) {
        std::cout << num << " ";
    }
    return 0;
}