[LeetCode]Binary Tree Zigzag Level Order Traversal

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 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

这道题是在Binary Tree Level Order Traversal的基础上多了一个条件：相邻两层的“左-右”顺序相反。增设一个变量level用来记录第几层，当level为偶数时，，将temp中的元素反转即可。 下面贴上代码：

/** * Definition for binary tree * 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> > ans;queue<TreeNode*> q;if (root == NULL)return ans;q.push(root);int nextCount = 0;int curCount = 1;int level = 0;vector<int> temp;while (!q.empty()){TreeNode* p = q.front();q.pop();temp.push_back(p->val);if (p->left){q.push(p->left);nextCount++;}if (p->right){q.push(p->right);nextCount++;}curCount–;if (!curCount){level++;if (level % 2 == 0){reverse(temp.begin(),temp.end());}ans.push_back(temp);temp=vector<int>();curCount = nextCount;nextCount = 0;}}return ans;}};

不然你大概会一直好奇和不甘吧——