面试题60 按之字形顺序打印二叉树

题目描述

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

 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 
12 class Solution {
13 public:
14     vector<vector<int>> v;
15     vector<int> vc;
16     stack<TreeNode*> s1;
17     stack<TreeNode*> s2;
18     queue<TreeNode*> q;
19     
20     vector<vector<int>> Print(TreeNode* pRoot) {
21         if (!pRoot)
22             return v;
23         q.push(pRoot);
24         while (!s1.empty() || !q.empty()){
25             while (!q.empty()){
26                 vc.push_back(q.front()->val);
27                 if (q.front()->left != NULL)
28                     s1.push(q.front()->left);
29                 if (q.front()->right != NULL)
30                     s1.push(q.front()->right);
31                 q.pop();
32             }
33             if (!vc.empty()){
34                 v.push_back(vc);
35                 vc.clear();
36             }
37             
38             while (!s1.empty()){
39                 vc.push_back(s1.top()->val);
40                 s2.push(s1.top());
41                 s1.pop();
42             }
43             while (!s2.empty()){
44                 if (s2.top()->left != NULL)
45                     q.push(s2.top()->left);
46                 if (s2.top()->right != NULL)
47                     q.push(s2.top()->right);
48                 s2.pop();
49             }  
50             if (!vc.empty()){
51                 v.push_back(vc);
52                 vc.clear();
53             }
54         }
55         return v;
56     }
57     
58 };