【题解】按之字形顺序打印二叉树

按之字形顺序打印二叉树

题目链接：按之字形顺序打印二叉树

解题思路：层次遍历，借助队列

首先解决如何模仿之字形的问题，我们为此设置一个flag，每到一层就修改flag，如果flag为true（初始为false的情况下），就逆序一下数组。

其次解决如何间隔每一层的问题，我们借助队列对实现，队列是先进先出的线性表，我们每一次让一层的节点进队列，在下一次循环中，让该层节点出队列，同时，让该层的子节点都进队列，这样，每次出队列的个数就是当前队列的大小，下一层要出队列的个数就等于这一层的子节点进队列的个数，也就是下一层的节点。由此，每层的节点数等于进入该层时队列长度，因为刚进入该层时，这一层每个节点都会push进队列，而上一层的节点都出去了。

具体做法：
首先进行判空，空树就返回空的res

其次建立辅助队列，同时初始化flag变量，根节点首先进入队列，作为第一次循环中的temp。

每进入一层，统计队列元素的个数，同时修改flag的值，每当访问一层，该层的子节点一定都加入队列，再下一层没加入，因此此时队列中的元素个数就是这一层的元素个数
遍历这一层这么多的节点数，出队，加入到该层的数组中，如果有子节点，就让每个节点的子节点进队

访问完该层元素后，根据flag的值决定该层对应的数组是否反转加入res中。

代码如下：

    vector<vector<int> > Print(TreeNode* pRoot) {TreeNode* head = pRoot;vector<vector<int>> res;if(pRoot == nullptr) return res;queue<TreeNode*> temp;//辅助队列temp.push(head);//根节点先进队TreeNode* p;bool flag = true;//初始化flag标志位while (!temp.empty()) {//记录二叉树的某一行vector<int> row;int n = temp.size();flag = !flag;//每进入一列，更改标志位for(int i=0; i<n; ++i){p = temp.front();temp.pop();row.push_back(p->val);//有子节点进队，这样上一层出队，下一层进队，保证了队列大小就是下一层节点个数if(p->left) temp.push(p->left);if(p->right) temp.push(p->right);}if(flag) reverse(row.begin(), row.end());//反转数组，模仿之字形的遍历效果res.push_back(row);//将该层放入结果数组中}                      return res;       }

解题思路2：借助栈

元素反转我们很容易想到栈，我们在此借助两个栈来实现之字形输出

首先栈1实现正序的层的元素输出，这样就要求我们在逆序输出的层中，先让右子树进栈，再让左子树进栈，反之，对于下一层需要逆序输出的，我们就先让左子树进栈，再让右子树进栈

具体步骤：
首先判空，空树返回空的res

建立两个辅助栈，根节点先进入栈1

当某个栈不空的时候，我们进入循环，在循环中，让下一层子树进入到相应的栈中，让该栈（该层）元素进入数组中，最后如果数组不空，就加入最后结果集中

根据访问的次序，栈1放入的是奇数层，也就是正常顺序输出的层，在该层中，让该层的子树按照先左后右的顺序加入栈2，这样在访问栈2的元素的时候就是按照逆序访问的，偶数层相反，在访问栈2时，将栈2中节点的子树按照先右后左的顺序加入栈1中，这样再访问栈1的时候，就是按照
先左再右的顺序访问了

每次访问完一层，即一个栈为空，则将一维数组加入二维数组中，并清空数组以便下一层用来记录，需要注意的是，将temp数组加入结果集res中一定要注意temp是否为空，因为存在一次外层循环，只有一个栈在其中放入元素的情况

代码如下：

    vector<vector<int> > Print(TreeNode* pRoot) {TreeNode* head = pRoot;vector<vector<int>> res;if(head == nullptr) return res;stack<TreeNode*> s1;stack<TreeNode*> s2;s1.push(head);while(!s1.empty() || !s2.empty()){vector<int> temp;while(!s1.empty()){TreeNode* node = s1.top();temp.push_back(node->val);if(node->left) s2.push(node->left);if(node->right) s2.push(node->right);s1.pop();}if(temp.size()) res.push_back(temp);temp.clear();while(!s2.empty()){TreeNode* node = s2.top();temp.push_back(node->val);if(node->right) s1.push(node->right);if(node->left) s1.push(node->left);s2.pop();}if(temp.size()) res.push_back(temp);}return res;}