103. Binary Tree Zigzag Level Order Traversal

problem description

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

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

algorithm thought

zigzag层次遍历，分析之后得知，可以用两个栈来辅助遍历。参差遍历本来是用一个队列就行。但是这个用两个栈，然后定义一个bool变量指定现在是左到右还是右到左，分别用一个栈辅助遍历。最后处理方式和层次遍历一样

使用两个栈的方法肯定还有优化的地方，去看了discuss之后，发现可以直接使用一个队列来做。最后遍历的结果需保存在一个vector中，我们默认只能push_back但是其实可以先定义好vector，最后看情况从左右分别将结果放置进去。

code

//use two stack 
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        stack<TreeNode*> q1,q2;
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        bool bo=true;
        q1.push(root);
        while(true){
            if(bo){
                vector<int> ve;
                while(!q1.empty()){
                    TreeNode* tmp=q1.top();
                    q1.pop();
                    if(tmp==NULL)
                        break;
                    ve.push_back(tmp->val);
                    if(tmp->left)
                        q2.push(tmp->left);
                    if(tmp->right)
                        q2.push(tmp->right);
                }
                res.push_back(ve);
                bo=false;
                if(q2.empty())
                    break;
            }
            else{
                vector<int> ve;
                while(!q2.empty()){
                    TreeNode* tmp=q2.top();
                    q2.pop();
                    if(tmp==NULL)
                        break;
                    ve.push_back(tmp->val);
                    if(tmp->right)
                        q1.push(tmp->right);
                    if(tmp->left)
                        q1.push(tmp->left);
                }
                res.push_back(ve);
                bo=true;
                if(q1.empty())
                    break;
            } 
        }
        return res;
    }
};


//use one queue
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(root==NULL)
            return res;
        bool leftToRight=true;
        TreeNode* tmp = new TreeNode(-1);
        q.push(root);q.push(tmp);
        vector<int> ve(1);
        int i=0;
        while(true){
            TreeNode* t=q.front();
            q.pop();
            if(t==tmp){
                res.push_back(ve);
                ve.clear();
                ve.resize(q.size());
                if(q.empty())
                    break;
                q.push(tmp);
                leftToRight=!leftToRight;
                i=0;
                continue;
            }
            if(t->left)
                q.push(t->left);
            if(t->right)
                q.push(t->right);
            if(leftToRight){
                ve[i]=t->val;
            }else{
                ve[ve.size()-i-1]=t->val;
            }
            i++;
        }
        return res;
    }
};

algorithm analysis

遍历问题时间复杂度还是一样的，都是O(n)