题解 | #二叉树的之字形层序遍历#

题解一： 层次遍历
解题思路： 通过一个level参数用来指示本层需要如何将队列中的元素填入到向量中。
分析：
1.首先初始化level = 0,如果level%2==0，则本层是从左往右打印； 如果level%2 == 1,则本层从右往左打印；
2. 因为每次将一层节点加入到队列之后，我们都可以知道队列保存值的数量，所以我们只需要控制填入向量中的顺序就行。
图示：

复杂度分析：
时间复杂度：O(N) 每个节点遍历一次
空间复杂度：O(N)
实现如下：

class Solution {
public:
    /**
     *
     * @param root TreeNode类
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        // write code here
        if(!root) return {};  //空树直接返回
        vector<vector<int> >ans;
        queue<TreeNode*> q;
        q.push(root);
        int level = 0;  //控制填入向量的顺序
        while(!q.empty()){
            int size = q.size(); //队列中含有的节点数量
            vector<int> tmp(size);
            for(int i = 0;i<size;i++){
                TreeNode* node = q.front(); //取出元素
                q.pop();
                if(level%2 == 0) tmp[i] = node->val; //如果level%2==0 ,从向量头开始填入元素
                else tmp[size-i-1] = node->val;     //否则，从尾开始填入元素
                if(node->left) q.push(node->left);  
                if(node->right) q.push(node->right);
        }
           ans.push_back(tmp);
           level++;  // level + 1
        }
        return ans;
    }
};

题解二： 深度优先
题解思路： 进行深度优先遍历，奇偶层节点使用不同插入方案。
图示：

复杂度分析：
时间复杂度：O(N)
空间复杂度：O(N) : 最坏情况树退化为链表

class Solution {
public:
    vector<vector<int> >ans;
    vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
        if(!root) return {};  //空树
        dfs(root,0);
        return ans;
    }
    void dfs(TreeNode* root,int level){
        if(!root) return; //递归边界
        if(level >= ans.size()) ans.resize(level+1); //为ans扩容
        if(level%2==0) ans[level].push_back(root->val); //level%2 ==0 ,插入到相应level向量的尾部
        else ans[level].insert(ans[level].begin(), root->val); //level%2 ==1 ,插入到相应level向量的头部
        dfs(root->left,level+1);
        dfs(root->right,level+1);
    }
};