Dare2Solve
This problem involves performing a level-order traversal of a binary tree in a zigzag pattern, alternating directions between levels.
To achieve the zigzag traversal:
O(n), where n is the number of nodes in the binary tree. Each node is processed exactly once.
O(n), in the worst case (completely unbalanced tree), the queue can contain all nodes at the maximum width of the tree.
class Solution {
public:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
if (!root) return {};
vector<vector<int>> result;
queue<TreeNode*> queueNodes;
queueNodes.push(root);
bool leftToRight = true;
while (!queueNodes.empty()) {
int size = queueNodes.size();
vector<int> level(size);
for (int i = 0; i < size; ++i) {
TreeNode* node = queueNodes.front();
queueNodes.pop();
int index = leftToRight ? i : size - 1 - i;
level[index] = node->val;
if (node->left) queueNodes.push(node->left);
if (node->right) queueNodes.push(node->right);
}
result.push_back(level);
leftToRight = !leftToRight;
}
return result;
}
};
class Solution:
def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
result = []
queue = deque([root])
left_to_right = True
while queue:
level_size = len(queue)
level_values = []
for _ in range(level_size):
node = queue.popleft()
if left_to_right:
level_values.append(node.val)
else:
level_values.insert(0, node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level_values)
left_to_right = not left_to_right
return result
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>(size);
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.add(node.val);
} else {
level.add(0, node.val);
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
leftToRight = !leftToRight;
}
return result;
}
}
var zigzagLevelOrder = function(root)
{
if (!root) return [];
let stackQueue = [root];
let result = [];
let level = 1;
while (stackQueue.length > 0) {
const isLtoR = level % 2 === 1;
const subLength = stackQueue.length;
const subList = [];
for (let i = 0; i < subLength; i++)
{
let node= stackQueue.shift();
if (isLtoR) {
subList.push(node.val);
} else {
subList.unshift(node.val);
}
if (node.left) stackQueue.push(node.left);
if (node.right) stackQueue.push(node.right);
}
level++;
result.push(subList);
}
return result;
};