Sponsored
Sponsored
This approach leverages the standard Breadth-First Search (BFS) algorithm to perform a level order traversal. We use a queue to traverse the tree level-by-level. For each level, we determine the order (left-to-right or right-to-left) by toggling a flag. At odd levels, we simply reverse the order of elements collected from the queue to achieve the zigzag effect.
Time Complexity: O(n), where n is the number of nodes in the tree, as each node is processed once.
Space Complexity: O(n), for storing the output and additional structures, like the queue used for BFS.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11 public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
12 List<List<Integer>> result = new ArrayList<>();
13 if (root == null) return result;
14
15 Queue<TreeNode> queue = new LinkedList<>();
16 queue.offer(root);
17 boolean leftToRight = true;
18
19 while (!queue.isEmpty()) {
20 int size = queue.size();
21 List<Integer> levelList = new ArrayList<>(size);
22 for (int i = 0; i < size; i++) {
23 TreeNode node = queue.poll();
24 if (leftToRight) {
25 levelList.add(node.val);
26 } else {
27 levelList.add(0, node.val);
28 }
29
30 if (node.left != null) queue.offer(node.left);
31 if (node.right != null) queue.offer(node.right);
32 }
33 result.add(levelList);
34 leftToRight = !leftToRight;
35 }
36 return result;
37 }
38}The Java solution employs a queue-based BFS framework with an extra layer of logic to manage insertion order based on the current level's direction. This is done by toggling a boolean flag and adding new values at the beginning or end of the current level's list accordingly.
In contrast to the BFS method, this approach utilizes Depth-First Search (DFS) for traversal. Recursive calls are made to process each node, and a hashmap (or similar structure) tracks the current depth. Depending on the depth, nodes are appended to the left or right of the current level list. This achieves the zigzag pattern as the recursion progresses.
Time Complexity: O(n), as DFS visits each node once.
Space Complexity: O(n), considering both storage needs for recursive calls and the result list.
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public IList<IList<int>> ZigzagLevelOrder(TreeNode root) {
IList<IList<int>> results = new List<IList<int>>();
dfs(root, 0, results);
return results;
}
private void dfs(TreeNode node, int depth, IList<IList<int>> results) {
if (node == null) return;
if (results.Count == depth) {
results.Add(new List<int>());
}
if (depth % 2 == 0) {
results[depth].Add(node.val);
} else {
results[depth].Insert(0, node.val);
}
dfs(node.left, depth + 1, results);
dfs(node.right, depth + 1, results);
}
}This C# solution applies DFS with tracking of an element's depth to insert values either at the front or back of the list depending on the zigzag direction required, which alternates every level.