原题链接

题目要求以“Z”字型遍历二叉树，并存储在二维数组里。

利用BFS，对每一层进行遍历。对于每一层是从左还是从右，用一个整数型判断当前是偶数行还是奇数行就可以了。

class Solution

{

public:

  vector<vector<int>> res;

  vector<vector<int>> zigzagLevelOrder(TreeNode *root)

  {

    if (root == NULL)

      return res;

    stack<TreeNode *> sta;

    sta.push(root);

    TravelNextLevel(sta, 1);

    return res;

  }

private:

  void TravelNextLevel(stack<TreeNode *> &sta, int level)

  {

    res.emplace_back();

    res.back().reserve(sta.size());

    stack<TreeNode *> nextSta;

    while (!sta.empty())

    {

      TreeNode *curNode = sta.top();

      sta.pop();

      res.back().push_back(curNode->val);

      if (level % 2 != 0)

      {

        if (curNode->left)

          nextSta.push(curNode->left);

        if (curNode->right)

          nextSta.push(curNode->right);

      }

      if (level % 2 == 0)

      {

        if (curNode->right)

          nextSta.push(curNode->right);

        if (curNode->left)

          nextSta.push(curNode->left);

      }

    }

    if (!nextSta.empty())

      TravelNextLevel(nextSta, level + 1);

  }

};