103. Binary Tree Zigzag Level Order Traversal
Last updated
Last updated
// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity : O(N), where NN is the number of nodes in the tree.
* - We visit each node once and only once.
* - In addition, the insertion operation on either end of the deque takes
* a constant time, rather than using the array/list data structure
* where the inserting at the head could take the O(K) time
* where K is the length of the list.
* Space complexity : O(N) where NN is the number of nodes in the tree.
* - The main memory consumption of the algorithm is the queue that we use
* for the loop, apart from the array that we use to keep the final output.
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> resultList = new ArrayList();
if(root == null) return resultList;
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
boolean leftToRight = true;
while(!queue.isEmpty()) {
int noOfNodes = queue.size();
LinkedList<Integer> levelList = new LinkedList<Integer>();
for(int i = 0; i < noOfNodes; i++) {
TreeNode node = queue.poll();
if(leftToRight) {
levelList.addLast(node.val);
} else {
levelList.addFirst(node.val);
}
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
resultList.add(levelList);
leftToRight = !leftToRight;
}
return resultList;
}
}/**
* Time complexity : O(N), where N is the number of nodes in the tree.
* Space complexity : O(H), where H is the height of the tree, i.e. the number
* of levels in the tree, which would be roughly log2(N).
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> resultList = new ArrayList();
if(root == null) return resultList;
helper(resultList, root, 0);
return resultList;
}
private void helper(List<List<Integer>> resultList,
TreeNode node,
int level) {
if(resultList.size() == level) {
resultList.add(new ArrayList<Integer>());
}
if(level % 2 == 0) {
resultList.get(level).add(node.val);
} else {
resultList.get(level).add(0, node.val);
}
if(node.left != null) {
helper(resultList, node.left, level+1);
}
if(node.right != null) {
helper(resultList, node.right, level+1);
}
}
}