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

亦凉 2023-01-22 06:53 94阅读 0赞

难度：中等  
题目描述：

> 给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]

/** * 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) { 
            vector<vector<int>> ans;
            if(root == nullptr){ 
                return ans;
            }
            queue<TreeNode*> q;
            q.push(root);
            int level=1;
            while(!q.empty()){ 
                vector<int> tmp;
                int cnt=q.size();
                for(int i=0;i<cnt;i++){ 
                    if(q.front()->left){ 
                        q.push(q.front()->left);
                    }
                    if(q.front()->right){ 
                        q.push(q.front()->right);
                    }
                    tmp.push_back(q.front()->val);
                    q.pop();
                }
                if(level%2==0){ 
                    reverse(tmp.begin(),tmp.end());
                }
                ans.push_back(tmp);
                level++;
            }
        return ans;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoYW9rdWRlenR0_size_16_color_FFFFFF_t_70]: /images/20221020/f0e0659d7e4d4773bddb3772665755ea.png