leetcode-103. 二叉树的锯齿形层序遍历

实战案例：

• 先是二叉树层序遍历，然后改成锯齿形遍历，除此之外，题目还要求符合一定的打印格式。一开始我是用的一个vector作为中间变量储存，然后面试官要求不用vector写一个优化的方法。然后我就考虑用双向队列。
• 阿里变体，n叉树，3层为周期反转
• BFS加一个标记sign，sign为false表示从左到右，元素append到最后，true表示从右到左，元素append到最前面。每遍历一层转换下sign（sign = !sign）
• 使用两个栈，利用栈的FILO特性实现反转
• 阿里面的时候考过这个题，我用了两个栈搞的哈哈哈，但是其实用个flag和一个count控制反转入栈的方向即可
• 双栈或者双端队列
• 微软算法题
• 记得用dfs实现一遍

BFS

2点需要注意：

1、使用deque双端队列；

2、使用isLeft2Right来表示从左向右，还是从右向左，最后变更方向。

代码中注释为重要的，即为于常规的层序遍历不同的地方，因为本题每一层保存的数组顺序是不同的。

class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        // 层序遍历的变体：使用双端队列
        vector<vector<int>> res;
        queue<TreeNode*> q;
        if (root) q.push(root);

        bool isLeft2Right = true; // 重要：初始第0层根节点是 从左往右
        while (!q.empty())
        {
            int qsize = q.size();
            // vector<int> tmp; 把vec变为 deque 双向队列
            deque<int> levelList; // 重要：用 deque代替vector存数值

            for (int i = 0; i < qsize; i++)
            {
                auto node = q.front();
                q.pop();

                // 重要：如果 isLeft2Right 为true，就把值放到 双端队列队尾，否则就放到队头
                if (isLeft2Right) 
                    levelList.push_back(node->val);
                else 
                    levelList.push_front(node->val);
                // tmp.push_back(node->val);

                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            // 重要：将deque队列保存到vector中，再放入res中
            vector<int> tmp(levelList.begin(), levelList.end());
            res.push_back(tmp);
            // 重要：修改存储方向
            isLeft2Right = !isLeft2Right;
        }
        return res;
    }
};

DFS

1、终止条件

2、层数level的判断条件

3、 如何保存val，根据level的奇偶判断

4、递归左右孩子节点

class Solution {
public:
    vector<vector<int>> res;
    void dfs(TreeNode* root, int level)
    {
        // 终止条件
        if (root == NULL) return;

        // 如果 level >= res.size()说明下一层的集合还没创建，所以要先创建下一层的集合
        if (level >= res.size()) 
            res.push_back(vector<int>());

        // 普通的保存val
        // res[level].push_back(root->val);
        
        // 根据level选择在vector的前面还是后面保存val，若 level为偶，则在 vector 的后面追加保存元素；
        // 若为奇，则在vector的begin()开头插入值
        if (level % 2 == 0) res[level].push_back(root->val);
        else res[level].insert(res[level].begin(), root->val);

        dfs(root->left, level+1);
        dfs(root->right, level+1);
    }

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {

        dfs(root, 0); // 根节点层的 层数 level = 0
        return res;
    }
};