LeetCode103.二叉树的锯齿形层序遍历

更新: 5/29/2026 字数: 0 字 时长: 0 分钟

题目链接：103. 二叉树的锯齿形层序遍历

题目已经很清晰了，就是层序遍历，左一次右一次即可，层序遍历的思路很简单，用队列存储然后一层一层遍历即可。

那么锯齿形遍历又如何实现呢？只需要判断当前是奇数还是偶数行，偶数行就反转一下再push就好了。

参考代码如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        if(root == nullptr)return {};
        int tot = 0;
        queue<TreeNode*> q;
        vector<vector<int>> ans;
        q.push(root);
        while(!q.empty()) {
            vector<int> tmp;
            int size = q.size();
            for(int i = 0;i < size;i++) {
                TreeNode* node = q.front();
                tmp.push_back(node -> val);
                q.pop();
                if(node -> left) q.push(node -> left);
                if(node -> right) q.push(node -> right);
            }
            if(ans.size() % 2) reverse(tmp.begin(), tmp.end());
            ans.push_back(tmp);
        }
        return ans;
    }
};