Level Order Traversal

Binary Tree Preorder Traversal

• Time: O(N)
• Space: O(1)

// Level Order Traversal BFS
public List<List<Integer>> levelOrder_1(TreeNode root) {
    List<List<Integer>> ret = new ArrayList<List<Integer>>();
    if (root == null) {
        return ret;
    }
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> list = new ArrayList<>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        ret.add(list);
    }
    return ret;
}

// Level Order Traversal DFS
public List<List<Integer>> levelOrder_2(TreeNode root) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    helper(res, root, 0);
    return res;
}

public void helper(List<List<Integer>> res, TreeNode root, int height) {
    if (root == null) return;
    if (height >= res.size()) {
        res.add(new LinkedList<Integer>());
    }
    res.get(height).add(root.val);
    helper(res, root.left, height+1);
    helper(res, root.right, height+1);
}

Bottom-up level order traversal

public List<List<Integer>> levelOrderBottom(TreeNode root) {
    List<List<Integer>> ret = levelOrder(root);
    Collections.reverse(ret);
    return ret;
}

Zigzag Level Order Traversal

public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> ret = levelOrder(root);
    for (int i = 0; i < ret.size(); i++) {
        if (i % 2 == 1) {
            Collections.reverse(ret.get(i));
        }
    }
    return ret;
}