[leetcode] 103 Binary Tree Zigzag Level Order Traversal (Medium)

原题链接

题目要求以“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);}
};