NC14 按之字形顺序打印二叉树
情景提要
牛客题解系列，按照题号顺序开始。
NC14
01
题目描述
例如:
02
输入输出示例
输入:
{1,2,3,#,#,4,5}
输出:
[[1],[3,2],[4,5]]
03
题目分析
如果是第一次遇到二叉树的层序遍历问题，建议先看下一篇NC15。
本题的难点在于按之字形遍历。
case1: 可以使用双端队列，用一个标志位来判断是队头出还是队尾出。
case2:使用两个栈或者队列。那么到底用哪种，怎么用呢？实践出真知。只要进入的左右顺序和选的数据结构一致就行。我这里选了一种用栈的方法。示例如下：
st1: 1
st2: 2,3 左右
st1: 5,4 右左
通过自己实际推演一遍，具体方法就出来啦。
03
代码实现
方法
/*struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;TreeNode(int x) :val(x), left(NULL), right(NULL) {}};*/class Solution {public:// 两个栈来模拟vector<vector<int> > Print(TreeNode* pRoot) {stack<TreeNode*> st1;stack<TreeNode*> st2;if(pRoot) st1.push(pRoot);TreeNode* node;vector<vector<int>> res;vector<int> tmp;while(!st1.empty() || !st2.empty()){while(!st1.empty()){node = st1.top();st1.pop();tmp.push_back(node->val);if(node->left) st2.push(node->left);if(node->right) st2.push(node->right);}if(tmp.size()>0) {res.push_back(tmp);tmp.clear();}while(!st2.empty()){node = st2.top();st2.pop();tmp.push_back(node->val);if(node->right) st1.push(node->right);if(node->left) st1.push(node->left);}if(tmp.size()>0) {res.push_back(tmp);tmp.clear();}}return res;}};
04
总结
具体的实际模拟和推演，是解题的良剂。
两个栈，实现之字形遍历。