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},

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

这道题类似Binary Tree Level Order Traversal，链接：http://www.cnblogs.com/laihaiteng/p/3797748.html，不同点在于相邻层次的遍历顺序不同，可以基于前面这道题的算法，增加一个层次号标记，把偶数层的遍历顺序逆序，再添加到vector中即可。我下面的思路稍稍有些不同，是利用栈和层次号来实现当场的zigzag遍历，而不是先正常的BFS，再依据层次号做改变。

个人思路：

1、逐层处理，每层的节点都放入队列A中，并记录层次号

2、当A队列出队时，将出队的节点值存储到相应层次的vector<int>中，并将该节点入栈B

3、当A队列为空时，表明该层的节点已经处理完毕，该处理下一层的节点了，将该层的vector<int>放入总的vector<vector<int> >，然后判断层次号是奇数还是偶数，由于通过栈B将上一层节点逆序了，可以很方便地进行zigzag遍历，按照栈的出栈顺序，奇数就先将出栈节点的左孩子入队，然后右孩子入队，偶数则顺序相反，直到栈为空，此时下一层节点已经按照zigzag的顺序入队列A了，重复2-3的步骤，直到节点全部遍历完

代码：

 1 #include <stddef.h>
 2 #include <stack>
 3 #include <queue>
 4 #include <vector>
 5 
 6 using namespace std;
 7 
 8 struct TreeNode
 9 {
10     int val;
11     TreeNode *left;
12     TreeNode *right;
13     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
14 };
15 
16 class Solution
17 {
18 public:
19     vector<vector<int> > zigzagLevelOrder(TreeNode *root)
20     {
21         vector<vector<int> > total_result;
22         vector<int> level_result;
23         queue<TreeNode *> level_treeNode;
24         stack<TreeNode *> level_treeNode_bak;
25 
26         if (!root)
27         {
28             return total_result;
29         }
30 
31         int level_num = 1;
32         level_treeNode.push(root);
33 
34         while (!level_treeNode.empty())
35         {
36             TreeNode *current = level_treeNode.front();
37             level_treeNode.pop();
38             level_treeNode_bak.push(current);
39             level_result.push_back(current->val);
40 
41             //表明该层遍历完成
42             if (level_treeNode.empty())
43             {
44                 total_result.push_back(level_result);
45                 level_result.clear();
46                 ++level_num;
47 
48                 if (level_num % 2)
49                 {
50                     while (!level_treeNode_bak.empty())
51                     {
52                         current = level_treeNode_bak.top();
53                         level_treeNode_bak.pop();
54                         if (current->left)
55                         {
56                             level_treeNode.push(current->left);
57                         }
58                         if (current->right)
59                         {
60                             level_treeNode.push(current->right);
61                         }
62                     }
63                 }
64                 else
65                 {
66                     while (!level_treeNode_bak.empty())
67                     {
68                         current = level_treeNode_bak.top();
69                         level_treeNode_bak.pop();
70                         if (current->right)
71                         {
72                             level_treeNode.push(current->right);
73                         }
74                         if (current->left)
75                         {
76                             level_treeNode.push(current->left);
77                         }
78                     }
79                 }
80             }
81         }
82 
83         return total_result;
84     }
85 };

View Code

看了一下网上的几篇文章，思路差不多，都是基于BFS算法，然后按照层次号奇偶来进行遍历顺序的逆反