剑指offer系列48：按之字形顺序打印二叉树

做这个题，选对数据结构很重要。

之字形打印，说明单双数行的输出顺序不一致，因此需要用两个栈。一行的数据放在其中一个栈中，如果栈空了说明此行全部输出，因此换下一个栈。

 1 class Solution {
 2 public:
 3     vector<vector<int> > Print(TreeNode* pRoot) {
 4         vector<vector<int> > re;
 5         if (pRoot == NULL)
 6             return re;
 7         stack<TreeNode*> st[2];
 8 
 9         //这两个变量来控制两个栈的切换
10         int cur = 0;
11         int next = 1;
12         st[cur].push(pRoot);
13         vector<int> aux;
14         while (!st[0].empty()||!st[1].empty())
15         {
16             TreeNode *pnode = st[cur].top();
17             st[cur].pop();
18             aux.push_back(pnode->val);
19             if (cur == 0)//双数行：压栈顺序：左-》右，出栈顺序：右-》左
20             {
21                 if (pnode->left)
22                     st[next].push(pnode->left);
23                 if (pnode->right)
24                     st[next].push(pnode->right);
25             }
26             else//单数行：压栈顺序：右-》左，出栈顺序：左-》右
27             {
28                 if (pnode->right)
29                     st[next].push(pnode->right);
30                 if (pnode->left)
31                     st[next].push(pnode->left);
32             }
33             if (st[cur].empty())//栈空了说明一行走完了
34             {
35                 re.push_back(aux);
36                 aux.clear();
37                 cur = 1 - cur;
38                 next = 1 - next;
39             }
40 
41 
42         }
43         return re;
44 
45     }
46 
47 };