题解 | #按之字形顺序打印二叉树#
按之字形顺序打印二叉树
http://www.nowcoder.com/practice/91b69814117f4e8097390d107d2efbe0
题意：
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）.
方法一：
bfs层次遍历
思路：利用队列实现 bfs 层次遍历。重点：计算每一层时，要先记录当前队列的元素个数。（可以实现每层的遍历）之后，将非空的左儿子节点入队，将非空的右儿子节点入队。最后，将偶数层的 vector 反转。
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> res;
vector<int> v;
if(pRoot==nullptr)
return res;
queue<TreeNode*> q;//队列
q.push(pRoot);//根节点入队
int id=0;
while(!q.empty()){
int num=q.size();//记录当前队列的元素个数
v.clear();
id++;
while(num--){
auto t=q.front();//出队
q.pop();
v.push_back(t->val);
if(t->left){//将非空的左儿子节点入队
q.push(t->left);
}
if(t->right){//将非空的右儿子节点入队
q.push(t->right);
}
}
if(id%2==0){//将偶数层反转
reverse(v.begin(),v.end());
}
res.push_back(v);
}
return res;
}
};
时间复杂度：%2C%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E9%83%BD%E8%AE%BF%E9%97%AE%E4%B8%80%E9%81%8D%E3%80%82)
空间复杂度：%2C%E9%98%9F%E5%88%97%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二:
dfs 递归
思路：重点：记录每个节点的深度，而每一个的深度对应一个 vector。
因此，可以递归遍历每个节点，记录每个节点的深度。
最后，将偶数层的vector反转。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int> > Print(TreeNode* pRoot) {
dfs(pRoot,1);
for(int i=1;i<res.size();i+=2){//将偶数层的vector反转
reverse(res[i].begin(),res[i].end());
}
return res;
}
void dfs(TreeNode* root,int depth){
if(root==nullptr){
return;
}
if(res.size()<depth){//新建一层
res.push_back(vector<int>());
}
res[depth-1].push_back(root->val);
dfs(root->left,depth+1);//递归左儿子节点
dfs(root->right,depth+1);//递归右儿子节点
}
};
时间复杂度：空间复杂度：%2C%E9%80%92%E5%BD%92%E6%A0%88%E7%9A%84%E6%B7%B1%E5%BA%A6%E3%80%82)
美团HR面1379人在聊
投递汇丰科技等公司8个岗位
