之字形打印二叉树

思路：借鉴层次遍历,设置方向标识。到每层时改变方向

vector<vector<int>> ZipPrint(TreeNode* root)
{
  vector<vector<int>> seq;
  if(root == NULL) return seq;
  vector<int> left;
  vector<int> right;
  bool forward = true;
  
  queue<TreeNode* > Q;
  TreeNode* p = root;
  TreeNode* last = root;
  Q.push(root);

  while(!Q.empty())
  {
    p = Q.front();
    if(forward) 
      left.push_back(p->val);
    else
      right.push_back(p->val);
    if(p->left)
      Q.push(p->left);
    if(p->right)
      Q.push(p->right);
    if(p == last)
      { // 一层结束
          if(forward)
          {
            seq.push_back(left);
            left.clear();
            forward = false;
          }
          else
          {
            reverse(right.begin(), right.end()); // 反向，用栈也可以
            seq.push_back(right);
            right.clear();
            forward = true;  
          }
      last = Q.back();
      }
    }
  return seq;
}