• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root)
return {};

vector<vector<int>> ans;
deque<TreeNode*> q{{root}};
bool isLeftToRight = true;

while (!q.empty()) {
vector<int> currLevel;
for (int sz = q.size(); sz > 0; --sz)
if (isLeftToRight) {
TreeNode* node = q.front();
q.pop_front();
currLevel.push_back(node->val);
if (node->left)
q.push_back(node->left);
if (node->right)
q.push_back(node->right);
} else {
TreeNode* node = q.back();
q.pop_back();
currLevel.push_back(node->val);
if (node->right)
q.push_front(node->right);
if (node->left)
q.push_front(node->left);
}
ans.push_back(currLevel);
isLeftToRight = !isLeftToRight;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();

List<List<Integer>> ans = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>(Arrays.asList(root));
boolean isLeftToRight = true;

while (!q.isEmpty()) {
List<Integer> currLevel = new ArrayList<>();
for (int sz = q.size(); sz > 0; --sz)
if (isLeftToRight) {
TreeNode node = q.pollFirst();
if (node.left != null)
if (node.right != null)
} else {
TreeNode node = q.pollLast();
if (node.right != null)
if (node.left != null)
}
isLeftToRight = !isLeftToRight;
}

return ans;
}
}
``````

## Python

``````class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []

ans = []
q = deque([root])
isLeftToRight = True

while q:
currLevel = []
for _ in range(len(q)):
if isLeftToRight:
node = q.popleft()
currLevel.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
else:
node = q.pop()
currLevel.append(node.val)
if node.right:
q.appendleft(node.right)
if node.left:
q.appendleft(node.left)
ans.append(currLevel)
isLeftToRight = not isLeftToRight

return ans
``````

• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root)
return {};

vector<vector<int>> ans;
queue<TreeNode*> q{{root}};
bool isLeftToRight = true;

while (!q.empty()) {
const int size = q.size();
vector<int> currLevel(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = q.front();
q.pop();
const int index = isLeftToRight ? i : size - i - 1;
currLevel[index] = node->val;
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
ans.push_back(node);
isLeftToRight = !isLeftToRight;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null)
return new ArrayList<>();

List<List<Integer>> ans = new ArrayList<>();
Deque<TreeNode> q = new ArrayDeque<>(Arrays.asList(root));
boolean isLeftToRight = true;

while (!q.isEmpty()) {
List<Integer> currLevel = new ArrayList<>();
for (int sz = q.size(); sz > 0; --sz) {
TreeNode node = q.poll();
if (isLeftToRight)
else
if (node.left != null)
q.offer(node.left);
if (node.right != null)
q.offer(node.right);
}
isLeftToRight = !isLeftToRight;
}

return ans;
}
}
``````

## Python

``````class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []

ans = []
q = deque([root])
isLeftToRight = True

while q:
size = len(q)
currLevel = [0] * size
for i in range(size):
node = q.popleft()
index = i if isLeftToRight else size - i - 1
currLevel[index] = node.val
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(currLevel)
isLeftToRight = not isLeftToRight

return ans
``````