本题也属于层次遍历的变形,不同之处在于其遍历的方法是交替进行的,形成一个ZigZag的曲线形式,如下:
代码如下:
1 struct TreeNode {
2 int val;
3 TreeNode* left;
4 TreeNode* right;
5 TreeNode(int x): val(x), left(NULL),right(NULL) {}
6 };
7
8 void Swap(vector<int> &ivec)
9 {
10 int temp = 0;
11 int len = ivec.size();
12 for (int i = 0; i < len/2; i ++) {
13 temp = ivec.at(i);
14 ivec.at(i) = ivec.at(len-1-i);
15 ivec.at(len-1-i) = temp;
16 }
17 }
18
19 vector<vector <int> > zigzagLevelOrder(TreeNode *root)
20 {
21 vector<vector<int> > tree_vector;
22 vector<int> ivec;
23 queue<TreeNode *> tree_queue;
24 if (NULL == root)
25 return tree_vector;
26
27 tree_queue.push(root);
28 tree_queue.push(NULL);
29 int nLevelCount = 1;
30 while (true) {
31 TreeNode *pTemp = tree_queue.front();
32 tree_queue.pop();
33 if (pTemp == NULL) {
34 if (nLevelCount%2 == 0) { //if the num of level is odd, swap the ivec;
35 Swap(ivec);
36 }
37 tree_vector.push_back(ivec);
38 ivec.clear();
39 if (tree_queue.empty())
40 break;
41 tree_queue.push(NULL);
42 nLevelCount ++;
43 }
44 else {
45 ivec.push_back(pTemp->val);
46 if (pTemp->left)
47 tree_queue.push(pTemp->left);
48 if (pTemp->right)
49 tree_queue.push(pTemp->right);
50 }
51 }
52 return tree_vector;
53 }