模板AVL树遍历返回vector仅存储根节点问题求解

你代码的核心问题是递归调用产生的左右子树遍历结果没有被合并：每次调用treeTraversal(node->left)、treeTraversal(node->right)都会生成对应子树的value集合，但你直接丢弃了这两个返回结果，仅在当前函数的临时vector中插入了当前节点的值，最终返回的vector就只会包含根节点的数据。
你之前直接在递归逻辑中用cout输出能拿到所有值，是因为打印操作不需要汇总返回结果，每次递归直接输出当前节点即可，但存储到vector需要把所有子节点的遍历结果汇总到同一个容器中。

有两种常用的修复方式：

方式1：保留返回vector的写法，合并子递归结果 #

这种方式和你原来的代码结构最接近，只需要把左右子树的返回结果合并到当前临时vector中即可：

vector<s> treeTraversal(){
     return treeTraversal(root);
}

vector<s> treeTraversal(AVLNode<t, s> *node ){
    vector<s> temp;

    if(node != nullptr){
        // 合并左子树遍历结果
        auto leftRes = treeTraversal(node->left);
        temp.insert(temp.end(), leftRes.begin(), leftRes.end());
        // 合并右子树遍历结果
        auto rightRes = treeTraversal(node->right);
        temp.insert(temp.end(), rightRes.begin(), rightRes.end());
        // 插入当前节点值（当前写法为后序遍历顺序，可根据需要调整插入位置）
        temp.push_back(node->vectorToBe);
    }

    return temp;
}

方式2：传引用存储结果，效率更高 #

这种方式避免了每次递归创建新vector、合并vector的开销，性能更优：

// 对外公共接口
vector<s> treeTraversal(){
    vector<s> result;
    treeTraversal(root, result);
    return result;
}

// 私有递归辅助函数
void treeTraversal(AVLNode<t, s> *node, vector<s>& result){
    if(node == nullptr) return;
    treeTraversal(node->left, result);
    treeTraversal(node->right, result);
    result.push_back(node->vectorToBe);
}

注：如果需要调整遍历顺序（前序/中序/后序），只需要调整push_back和左右子树递归调用的先后顺序即可。

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