Binary Tree Zigzag Level Order Traversal.png
解題思路 ：
主要是 BFS 用 queue 來實現 level order traversal 只是其中多加了一個 boolean 變數來決定是否要反向放入某一層的數值 我用 xor 來做 boolean 值的修改 另外 c++ 有內建的 reverse 函數 只要放入 vector 的 begin 跟 end 即可使用
C++ code :
<pre><code>
/**
- Definition of TreeNode:
- class TreeNode {
- public:
int val;TreeNode *left, *right;TreeNode(int val) {this->val = val;this->left = this->right = NULL;}- }
*/
class Solution {
/**
* @param root: The root of binary tree.
* @return: A list of lists of integer include
* the zigzag level order traversal of its nodes' values
*/
public:
vector<vector<int>> zigzagLevelOrder(TreeNode *root) {
// write your code here
vector<vector<int>> res;
if(!root) return res;
vector<int> tmp;
queue<TreeNode*> Q;
Q.push(root);
bool leftToRight = false;
while(!Q.empty())
{
int n = Q.size();
for(int i = 0; i < n; i++)
{
TreeNode *node = Q.front();
Q.pop();
tmp.push_back(node->val);
if(node->left) Q.push(node->left);
if(node->right) Q.push(node->right);
}
leftToRight ^= 1;
if(!leftToRight) reverse(tmp.begin(), tmp.end());
res.emplace_back(tmp);
tmp.clear();
}
return res;
}
};
