剑指offer 按之字形顺序打印二叉树

题目：

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

代码：

 1 /*
 2 struct TreeNode {
 3     int val;
 4     struct TreeNode *left;
 5     struct TreeNode *right;
 6     TreeNode(int x) :
 7             val(x), left(NULL), right(NULL) {
 8     }
 9 };
10 */
11 class Solution {
12 public:
13     stack<TreeNode*> st1; //存放奇数层结点
14     stack<TreeNode*> st2; //存放偶数层结点
15     vector<vector<int> > List;
16     vector<vector<int> > Print(TreeNode* pRoot) {
17         if(pRoot == NULL) return List;
18         int pattern = 1;
19         vector<int> list;
20         st1.push(pRoot);
21         list.push_back(pRoot->val);
22         List.push_back(list);
23         list.clear();
24         while(!(st1.empty() && st2.empty())) {
25             TreeNode* temp;
26             //如果偶数层结点还未遍历完毕，则继续操作，先左结点后右节点
27             if(pattern == 2) {
28                 temp = st2.top();
29                 st2.pop();
30                 if(temp->left){
31                     st1.push(temp->left);
32                     list.push_back(temp->left->val);
33                 }
34                 if(temp->right){
35                     st1.push(temp->right);
36                     list.push_back(temp->right->val);
37                 }
38                 //如果堆栈为空，且list不为空，则说明该层遍历完毕，将其子节点序列记录，并清空list，改为st1遍历
39                 if(st2.empty() && !list.empty()){
40                     pattern = 1;
41                     List.push_back(list);
42                     list.clear();
43                 }
44             }
45             //如果奇数层结点还未遍历完毕，则继续操作，先右结点后左节点
46             else {
47                 temp = st1.top();
48                 st1.pop();
49                 if(temp->right){
50                     st2.push(temp->right);
51                     list.push_back(temp->right->val);
52                 }
53                 if(temp->left){
54                     st2.push(temp->left);
55                     list.push_back(temp->left->val);
56                 }
57                 if(st1.empty() && !list.empty()){
58                     pattern = 2;
59                     List.push_back(list);
60                     list.clear();
61                 }
62             }
63         }
64         return List;
65     }
66 };

我的笔记：

　　因为本题要求 之字形 打印，即先进后出使用栈来实现。为了思路简单，使用 两个栈 来实现要求。

将奇数行的结点存入 st1 栈，同时利用 list 来记录 栈中结点的左右子节点；
将偶数行的结点存入 st2 栈，同时利用 list 来记录 栈中结点的左右子节点；
当 当前使用的栈为空时，将 list 的内容压入 List ，并将 list 清空，并改为另一个栈来遍历。
直至 两栈都为空 是结束遍历。