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

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

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

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层序遍历如下：

[
  [3],
  [20,9],
  [15,7]
]

---

基本思路：最直接的想法是层次遍历，然后遇到奇数层时，直接逆转数组即可，不过这一定不是面试官想看见的吧。每一层的遍历方向可以改变，推荐双端队列来解决该问题。

• 一个中心点，两个基本点：
  • 一个中心点，要保持队形，不管你怎么入队，都要保持队列每层从左到右的顺序不变。
  • 两个基本点，正序从双端队列的前边出队，后边入队；逆序时，后边出队，前边入队。

    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        deque<TreeNode *> dq;
        vector<vector<int>> ans;
        if(root==nullptr)
            return ans;
        dq.push_back(root);
        bool ltor=true;
        while(!dq.empty()){
            int len=dq.size();
            vector<int> tmp;
            if(ltor){  //正序:前出后进
                for(int i=0;i<len;i++){
                    TreeNode *cur=dq.front();
                    dq.pop_front();
                    tmp.emplace_back(cur->val);
                    if(cur->left)
                        dq.push_back(cur->left);
                    if(cur->right)
                        dq.push_back(cur->right);
                }
            }
            else{  //逆序:后出前进
                for(int i=0;i<len;i++){
                    TreeNode *cur=dq.back();
                    dq.pop_back();
                    if(cur->right)
                        dq.push_front(cur->right);  //注意保持队形，先右后左
                    if(cur->left)
                        dq.push_front(cur->left);
                    tmp.emplace_back(cur->val);
                }
            }
            ans.push_back(tmp);
            ltor=!ltor;
        }

        return ans;
    }

基本思路：也可以对tmp做手脚，令tmp(len,0),用队列层次遍历，每次出队都是从左往右，但是是奇数层时，，逆序赋值/从头部插入也可以即可,dfs类似的思路