如何使用指定接口的尾递归实现二叉树层序遍历并格式化输出

核心思路 #

原尾递归代码通过vector<vector<int>>按层级收集节点，现在要直接构建目标格式字符串，核心是在递归过程中先按层级缓存节点值，待所有节点遍历完成后（回到根节点的递归层级时），将缓存的层级数据拼接成指定格式的字符串。

代码实现 #

首先假设二叉树节点定义如下：

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

实现指定接口的函数：

#include <vector>
#include <string>

using namespace std;

void LevelOrderTraversalTailRecur(BinaryTreeNode* root, int level, string &s) {
    // 静态变量用于缓存各层节点值，递归过程中持续有效
    static vector<vector<int>> levelNodes;

    // 处理当前节点：将节点值加入对应层级的缓存
    if (root != nullptr) {
        if (level >= levelNodes.size()) {
            levelNodes.emplace_back();
        }
        levelNodes[level].push_back(root->val);

        // 尾递归遍历左右子树
        LevelOrderTraversalTailRecur(root->left, level + 1, s);
        LevelOrderTraversalTailRecur(root->right, level + 1, s);
    }

    // 回到根节点层级（level=0）时，拼接字符串
    if (level == 0) {
        for (size_t i = 0; i < levelNodes.size(); ++i) {
            // 拼接当前层的所有节点
            for (size_t j = 0; j < levelNodes[i].size(); ++j) {
                if (j != 0) {
                    s += ", ";
                }
                s += to_string(levelNodes[i][j]);
            }
            // 非最后一层，添加层分隔符
            if (i != levelNodes.size() - 1) {
                s += " : ";
            }
        }
        // 清空缓存，避免下次调用时残留数据
        levelNodes.clear();
    }
}

调用示例 #

#include <iostream>

int main() {
    // 构建示例二叉树
    //        60
    //      /    \
    //    50     100
    //   /  \      \
    // 30   55    1000
    BinaryTreeNode* root = new BinaryTreeNode(60);
    root->left = new BinaryTreeNode(50);
    root->right = new BinaryTreeNode(100);
    root->left->left = new BinaryTreeNode(30);
    root->left->right = new BinaryTreeNode(55);
    root->right->right = new BinaryTreeNode(1000);

    string result;
    LevelOrderTraversalTailRecur(root, 0, result);
    cout << result << endl; // 输出：60 : 50, 100 : 30, 55, 1000

    // 释放节点内存（省略具体释放逻辑）
    return 0;
}

关键细节说明 #

• 静态缓存的使用：因为接口参数固定，用静态vector<vector<int>>在递归过程中保存各层节点，确保所有递归调用共享同一缓存。
• 尾递归顺序：先处理当前节点，再递归左、右子树，保证所有节点按层级被收集。
• 字符串拼接规则：层内节点用, 分隔，层与层之间用:分隔，最后一层不添加多余分隔符。
• 缓存清空：每次根节点递归完成后清空静态缓存，避免多次调用时数据污染。
• 线程安全注意：如果是多线程场景，静态变量会存在竞争问题，可改用thread_local修饰缓存变量，确保每个线程拥有独立的缓存。

内容的提问来源于stack exchange，提问作者Willi