原题传送门—>>


题目描述：

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

例如：

  • 给定二叉树 [3,9,20,null,null,15,7],
  • 3
  • / \
  • 9 20
  • / \

  • 15 7
    返回锯齿形层次遍历如下：

  • [

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

层序遍历的plus版本

需要注意：
1：每次更新cur时需要将逆序遍历
2：左右子树的访问顺序时不停交替的

/**
 * 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>> ans; 
    vector<TreeNode*> pre;
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        int flag = 0;
        if(!root)
            return ans;
    pre.push_back(root);
    while(!pre.empty())
    {
        flag = 1- flag;
        vector<int> tmp;
        vector<TreeNode*> cur;
        if(flag) 
        {
            for(vector<TreeNode*>::reverse_iterator i = pre.rbegin(); i != pre.rend(); ++i)
            {
               tmp.push_back((*i)->val);
              if((*i)->left)
             {
                  cur.push_back((*i)->left);
             }
              if((*i)->right)
             {
                 cur.push_back((*i)->right);
             }
            }
        }
        else
        {
            for(vector<TreeNode*>::reverse_iterator i = pre.rbegin(); i != pre.rend(); ++i)
            {
               tmp.push_back((*i)->val);
              if((*i)->right)
             {
                 cur.push_back((*i)->right);
             }
            if((*i)->left)
             {
                  cur.push_back((*i)->left);
             }
            }
        }
        pre = cur;
        ans.push_back(tmp);
    }
        return ans;
    }
};