C++二叉树的层次遍历算法代码

C++中，层次遍历（也称为广度优先搜索，Breadth-First Search, BFS）通常使用队列数据结构来实现。以下是使用队列进行二叉树层次遍历的递归和非递归版本：

**递归层次遍历（Level Order Traversal, Recursive）：**

由于二叉树没有内置的层次结构，所以在这里我们假设有一个额外的函数`levelOrderHelper`辅助递归过程：

vector<vector<int>> levelOrderRecursive(TreeNode* root) {
    vector<vector<int>> result;
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel(levelSize);
        
        for (int i = 0; i < levelSize; ++i) {
            TreeNode* node = q.front();
            q.pop();
            currentLevel[i] = node->val;

            if (node->left) {
                q.push(node->left);
            }
            if (node->right) {
                q.push(node->right);
            }
        }
        
        result.push_back(currentLevel);
    }
    
    return result;
}

**非递归层次遍历（Level Order Traversal, Non-Recursive）：**

非递归版本则需要维护一个二维数组用于存储结果，并使用队列辅助遍历：

vector<vector<int>> levelOrderNonRecursive(TreeNode* root) {
    if (root == nullptr) return {};

    vector<vector<int>> result;
    queue<pair<TreeNode*, int>> q; // 二级队列，第一个元素是节点，第二个是层级
    q.push({root, 0});

    while (!q.empty()) {
        TreeNode* node = q.front().first;
        int level = q.front().second;
        q.pop();

        if (result.size() <= level) result.resize(level + 1); // 初始化当前层

        result[level].push_back(node->val);
        
        if (node->left) q.push({node->left, level + 1});
        if (node->right) q.push({node->right, level + 1});
    }

    return result;
}