C++ 递归打印AVL树遍历元素时如何去除末尾多余逗号

递归完全可以实现该需求，无需改为非递归遍历，下面提供两种常用实现思路：

思路1：遍历过程中直接输出（无额外存储空间） #

通过引用传递标记位记录是否是第一个输出的元素，第一个元素直接输出，后续元素先输出分隔逗号再输出值，从根源上避免尾部多余逗号。
实现代码如下：

// 内部递归函数
void inOrder(Node* root, bool& isFirst)
{
    if(root != nullptr) {
        inOrder(root->left, isFirst);
        if (isFirst) {
            cout << root->data;
            isFirst = false;
        } else {
            cout << ", " << root->data;
        }
        inOrder(root->right, isFirst);
    }
}

// 对外暴露的调用接口，保持原有参数不变
void inOrder(Node* root)
{
    bool isFirst = true;
    inOrder(root, isFirst);
    // 可选：末尾添加换行
    cout << endl;
}

该方案仅增加了一个布尔标记的空间开销，遍历的空间复杂度仍为AVL树的递归栈深度O(logn)，性能最优。

思路2：先收集结果再统一输出（逻辑更直观） #

如果不想修改原递归函数的核心逻辑，也可以先把所有遍历结果存入容器，最后遍历容器做格式化输出。
实现代码如下：

// 内部递归收集结果
void inOrder(Node* root, vector<int>& result)
{
    if(root != nullptr) {
        inOrder(root->left, result);
        result.push_back(root->data);
        inOrder(root->right, result);
    }
}

// 对外调用接口
void printInOrder(Node* root)
{
    vector<int> result;
    inOrder(root, result);
    for (int i = 0; i < result.size(); i++) {
        if (i != 0) {
            cout << ", ";
        }
        cout << result[i];
    }
    cout << endl;
}

该方案逻辑简单不易出错，还可以复用收集到的遍历结果，仅额外增加O(n)的存储空间，绝大多数场景下都适用。

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