题解 | #按之字形顺序打印二叉树#

class Solution {
public:
map<TreeNode,int> m;
#遍历二叉树，使用map存储每个节点的高度，此处使用前序遍历
void biaoji(TreeNode root,int n){
if(!root) return;
m[root] = n;
n++;
biaoji(root->left,n);
biaoji(root->right,n);
return;
}
#层序遍历读取每个节点，存储于v中
void bianli(TreeNode* root,vector<TreeNode> &v){
queue<TreeNode> q;
TreeNode* temp;
q.push(root);
while(!q.empty()){
temp = q.front();
v.push_back(temp);
q.pop();
if(temp->left) q.push(temp->left);
if(temp->right) q.push(temp->right);
}
return;
}
#遍历v，以高度为分界，m[v[i]]为奇数直接push参数val至temp中；m[v[i]]为偶数利用栈存取后取出。
vector<vector<int> > Print(TreeNode* pRoot) {
vector<TreeNode*> v;
vector<int> temp;
vector<vector<int>>vv;
stack<int> s;
if(!pRoot) return {};
biaoji(pRoot,1);
bianli(pRoot, v);
for(int i=0;i<v.size();i++){
if(m[v[i]]%2==1){
temp.push_back(v[i]->val);}
else{
s.push(v[i]->val);
}
if(m[v[i]]!=m[v[i+1]]){
while(!s.empty()){
temp.push_back(s.top());
s.pop();
}
vv.push_back(temp);
temp.clear();
}
}
return vv;
}</int></int></int></int>

};