二叉树ZigZag遍历C++代码问题：非平衡树测试用例出错求助

你的代码核心问题在于遍历逻辑的设计错误：你让父节点负责将子节点的数据添加到下一层的集合中，而非让每个节点自己处理当前层的数据后再递归处理子节点。这种设计会导致节点层级混乱、数据添加时机错误，尤其在非平衡树中会出现数据遗漏或错误添加的情况。

具体问题点拆解 #

1. 层级与数据添加逻辑颠倒：
   你的order函数中，父节点直接访问子节点的data并添加到level+1的集合中，完全违背了递归遍历的原则——应该让子节点在递归过程中自主把数据加入对应层级的集合。
2. k=1分支逻辑混乱：
   在k==1的分支里，你先递归左右子树，再尝试添加子节点的数据到level+1，此时递归已经处理了下一层级，导致数据被错误地重复添加或层级错位。
3. 初始调用参数错误：
   在zigzag函数中，你初始将根节点数据放入ans[0]，然后调用order(root, ans, 1, 1)，这里的level参数设置为1，会导致后续层级的偏移，和实际遍历层级不匹配。

修复后的实现方案 #

推荐两种更清晰的ZigZag遍历实现方式：

方案1：DFS深度优先遍历（记录层级，按需调整顺序）

这种方式通过递归记录当前节点的层级，将数据加入对应层级的集合，在添加时直接根据层级奇偶性调整顺序：

#include <vector>
#include <algorithm>
using namespace std;

struct node {
    int data;
    node* left;
    node* right;
};

void dfs(node* root, vector<vector<int>>& ans, int level) {
    if (!root) return;
    // 如果当前层级的集合未初始化，先创建空集合
    if (ans.size() == level) {
        ans.push_back({});
    }
    // 偶数层（从0开始）从左到右添加，奇数层从右到左添加（通过插在头部实现）
    if (level % 2 == 0) {
        ans[level].push_back(root->data);
    } else {
        ans[level].insert(ans[level].begin(), root->data);
    }
    // 递归遍历左右子节点（先左后右，配合头部插入实现奇数层的逆序）
    dfs(root->left, ans, level + 1);
    dfs(root->right, ans, level + 1);
}

vector<vector<int>> zigzag(node* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    dfs(root, ans, 0);
    return ans;
}

方案2：BFS广度优先遍历（按层处理，切换顺序）

这种方式更直观，按层遍历二叉树，每处理完一层后根据标记决定是否反转该层数据：

#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

struct node {
    int data;
    node* left;
    node* right;
};

vector<vector<int>> zigzag(node* root) {
    vector<vector<int>> ans;
    if (!root) return ans;
    queue<node*> q;
    q.push(root);
    bool leftToRight = true; // 标记当前层是否从左到右遍历

    while (!q.empty()) {
        int levelSize = q.size();
        vector<int> currentLevel(levelSize);

        for (int i = 0; i < levelSize; ++i) {
            node* curr = q.front();
            q.pop();
            // 根据当前顺序标记，决定数据存入当前层的位置
            int idx = leftToRight ? i : (levelSize - 1 - i);
            currentLevel[idx] = curr->data;
            // 加入下一层节点
            if (curr->left) q.push(curr->left);
            if (curr->right) q.push(curr->right);
        }

        ans.push_back(currentLevel);
        leftToRight = !leftToRight; // 切换下一层的遍历顺序
    }
    return ans;
}

测试验证 #

针对你给出的第一个测试用例：

3
 / \
9  20
   / \
  15  7

修复后的代码会返回[[3], [20, 9], [15, 7]]，输出结果为3 20 9 15 7，符合ZigZag遍历的预期。

第二个测试用例：

3
   / \
  9  20
 /   / \
1   15  7

修复后的代码会返回[[3], [20, 9], [1, 15, 7]]，输出结果为3 20 9 1 15 7，也符合预期。

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