二叉树Z形层序遍历
二叉树的之字形层序遍历
http://www.nowcoder.com/questionTerminal/47e1687126fa461e8a3aff8632aa5559
题目描述
给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）
解法
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> ans;
if (root == nullptr) {
return ans;
}
queue<TreeNode*> que;
que.push(root);
bool isOrderLeft = true;
while (!que.empty()) {
int levelSize = que.size();
list<int> levelList;
for (int i = 0; i < levelSize; i++) {
TreeNode* curNode = que.front();
que.pop();
// Z形
if (isOrderLeft) {
levelList.push_back(curNode->val);
} else {
levelList.push_front(curNode->val);
}
// 层序
if (curNode->left) que.push(curNode->left);
if (curNode->right) que.push(curNode->right);
}
vector<int> levelVec(levelList.begin(), levelList.end());
ans.push_back(levelVec);
// Z形: 方向一层一变换
isOrderLeft = !isOrderLeft;
}
return ans;
}