【宽搜】4. leetcode 103 二叉树的锯齿形层序遍历

1 题目描述

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

2 题目解析

根据题目描述，第一行是从左往右遍历，第二行是从右往左遍历。和层序遍历的区别就是：
在偶数行需要从右往左遍历。

因此，只需要在层序遍历的基础上增加一个变量判断层数，如果是奇数层就不需要改变vector，如果是偶数层就将该层的vector逆转一下。

我在这篇文章中讲解了宽度优先遍历的模板，如果没有看的同学可以先去看一下。

代码

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        queue<TreeNode*> q;

        if (root == nullptr)
            return res;
        
        q.push(root);
        //判断层数 --> n是递增的，所以在外面定义
        int n = 1;
        while(q.size())
        {
            vector<int> tmp;
            int sz = q.size();
           
            //对每一层进行操作   
            for (int i = 0; i < sz; ++ i)
            {
                TreeNode* t = q.front();
                q.pop();

                if (t->left)
                    q.push(t->left);
                if (t->right)
                    q.push(t->right);
                
                tmp.push_back(t->val);
            }

            //是偶数就要逆置一下
            if (n % 2 == 0)
                reverse(tmp.begin(), tmp.end());

            //注意顺序，需要先逆转再增加n的值，不然会出现完全相反的结果    
            ++ n;
            res.push_back(tmp);
        }

        return res;
    }
};