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

题目描述

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

解题思路

考虑用两个栈分别记录各层节点：s1记录奇数层节点，s2记录偶数层节点。首先把根节点推入s1，设置bool型变量isOdd记录是否为奇数层并置为true，然后开始遍历二叉树：

若该层为奇数层，则取出s1栈顶结点，将其加入到vector中，并依次把其左子节点、右子节点加入栈s2，这样偶数层从s2栈顶开始打印的顺序就是从右至左。若s1中结点已全部被取出，说明该奇数层已打印完毕，所以将vector加入到解集中，并清空此vector，然后将isOdd置为false。
若该层为偶数层，则取出s2栈顶结点，将其加入到vector中，并依次把其右子节点、左子节点加入栈s1，这样奇数层从s1栈顶开始打印的顺序就是从左至右。若s2中结点已全部被取出，说明该偶数层已打印完毕，所以将vector加入到解集中，并清空此vector，然后将isOdd置为true。

最后若两个栈均为空，说明二叉树已打印完毕，返回vector的集合。

代码

 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     vector<vector<int> > Print(TreeNode* pRoot) {
14         vector<vector<int> > vs;
15         if(pRoot){
16             stack<TreeNode*> s1,s2;
17             s1.push(pRoot);
18             bool isOdd=true;
19             vector<int> v;
20             while(s1.size()||s2.size()){
21                 //奇数层依次把左子节点、右子节点加入栈s2
22                 if(isOdd){
23                     TreeNode* node=s1.top();
24                     s1.pop();
25                     v.push_back(node->val);
26                     if(node->left)
27                         s2.push(node->left);
28                     if(node->right)
29                         s2.push(node->right);
30                     if(s1.empty()){
31                         isOdd=false;
32                         vs.push_back(v);
33                         v.clear();
34                     }
35                 }
36                 //偶数层依次把右子节点、左子节点加入栈s1
37                 else{
38                     TreeNode* node=s2.top();
39                     s2.pop();
40                     v.push_back(node->val);
41                     if(node->right)
42                         s1.push(node->right);
43                     if(node->left)
44                         s1.push(node->left);
45                     if(s2.empty()){
46                         isOdd=true;
47                         vs.push_back(v);
48                         v.clear();
49                     }
50                 }
51             }
52         }
53         return vs;
54     }
55     
56 };