一. 题目描述
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,#,#,15,7,
3 / \ 9 20/ \ 15 7
二. 题目分析
BFS，这里用一个bool记录是从左到右还是从右到左读取数据，每一层遍历结束就翻转一下。
三. 示例代码
;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){vector<vector<int> > result;Traverse(root, 1, result, true);return result;}private:void Traverse(TreeNode *root, size_t level, vector<vector<int> > & result, bool leftToRight){if (root == NULL) return;if (level > result.size())result.push_back(vector<int>());if (leftToRight)result[level – 1].push_back(root->val);elseresult[level – 1].insert(result[level – 1].begin(), root->val);Traverse(root->left, level + 1, result, !leftToRight);Traverse(root->right, level + 1, result, !leftToRight);}};
四. 小结
比Binary Tree Level Order Traversal 和Binary Tree Level Order Traversal II 稍微难一些，需要注意更多细节。
，当你能梦的时候就不要放弃梦
