10.4 Binary Tree Level Order Traversal (Easy)

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example: Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

https://leetcode.com/problems/binary-tree-level-order-traversal/

public List<List<Integer>> levelOrder(Node root) {
    List<List<Integer>> ListResult = new ArrayList<List<Integer>>();
    if (root == null)
        return ListResult;

    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        List<Integer> currentList = new ArrayList<Integer>();
        int levelNode = queue.size();

        while (levelNode > 0) {
            Node temp = queue.poll();
            currentList.add(temp.value);
            if (temp.left != null)
                queue.offer(temp.left);
            if (temp.right != null)
                queue.offer(temp.right);
            levelNode--;
        }
        ListResult.add(currentList);
        System.out.println(ListResult);
    }
    return ListResult;
}

Binary Tree Zigzag Level Order Traversal (Medium)

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example: Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

In the above question, we use ArrayList inside the while loop; but for Zigzag Level, we need to use LinkedList instead.

public List<List<Integer>> zigzagLevelOrder3(Node root) {
    List<List<Integer>> ListResult = new ArrayList<List<Integer>>();
    if (root == null)
        return ListResult;

    boolean isNormalDirection = true;
    Queue<Node> queue = new LinkedList<Node>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        LinkedList<Integer> currentList = new LinkedList<Integer>();

        int levelNode = queue.size();
        while (levelNode > 0) {
            Node temp = queue.poll();
            if (isNormalDirection) {
                currentList.add(temp.value);
            } else {
                currentList.addFirst(temp.value);
            }

            if (temp.left != null)
                queue.offer(temp.left);
            if (temp.right != null)
                queue.offer(temp.right);
            levelNode--;
        }

        System.out.println(currentList);
        ListResult.add(currentList);
        isNormalDirection = !isNormalDirection;
    }
    return ListResult;
}

located@ package bst.BreadthFirstTraversal.java