用c++递归算法实现二叉树的层次遍历

二叉树的层次遍历可以使用队列实现，不过也可以使用递归实现。具体实现过程如下：

首先，我们需要先计算出二叉树的深度，也就是最大层数。可以使用递归实现：

int maxDepth(TreeNode *root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

然后，我们可以从第一层开始，依次递归遍历每一层的节点。对于每一层，我们需要先遍历左子树，再遍历右子树。具体实现如下：

void printLevelOrder(TreeNode *root, int level) {
    if (!root) return;
    if (level == 1) {
        cout << root->val << " ";
    } else if (level > 1) {
        printLevelOrder(root->left, level - 1);
        printLevelOrder(root->right, level - 1);
    }
}

void levelOrderTraversal(TreeNode *root) {
    int depth = maxDepth(root);
    for (int i = 1; i <= depth; i++) {
        printLevelOrder(root, i);
    }
}

在 `levelOrderTraversal` 函数中，我们先计算出二叉树的深度，然后从第一层开始，依次遍历每一层的节点。对于每一层，我们调用 `printLevelOrder` 函数，打印出该层的节点。这个函数接受两个参数：当前节点和当前层数。如果当前层数为 1，就打印当前节点的值；否则，就递归遍历当前节点的左右子树，直到遍历到第一层为止。

完整的代码如下：

#include <iostream>

using namespace std;

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

int maxDepth(TreeNode *root) {
    if (!root) return 0;
    int leftDepth = maxDepth(root->left);
    int rightDepth = maxDepth(root->right);
    return max(leftDepth, rightDepth) + 1;
}

void printLevelOrder(TreeNode *root, int level) {
    if (!root) return;
    if (level == 1) {
        cout << root->val << " ";
    } else if (level > 1) {
        printLevelOrder(root->left, level - 1);
        printLevelOrder(root->right, level - 1);
    }
}

void levelOrderTraversal(TreeNode *root) {
    int depth = maxDepth(root);
    for (int i = 1; i <= depth; i++) {
        printLevelOrder(root, i);
    }
}

int main() {
    /*
     *      1
     *     / \
     *    2   3
     *   / \   \
     *  4   5   6
     */
    TreeNode *root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->right = new TreeNode(6);

    levelOrderTraversal(root); // 1 2 3 4 5 6

    return 0;
}