[LeetCode]102. Binary Tree Level Order Traversal

     A
    / \
  B   C
 / \     \
D E    F

(1) 2 queues
Q1: A
Q2: BC
Q1: DEF
Q2: [N]
Q1: [N]

(2) 1 queue + dummy node
Q: A#BC#DEF#

(3) 1 queue + queue.size

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (queue.size() != 0) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                level.add(node.val);
            }
            result.add(level);
        }
        return result;
    }
}

* Same if it's not binary tree

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class LevelOrder {
    static class TreeNode {
        int val;
        List<TreeNode> children;
        public TreeNode(int val, TreeNode...nodes) {
            this.val = val;
            this.children = new LinkedList<TreeNode>();
            for (TreeNode node : nodes) {
                this.children.add(node);
            }
        }
        public int getVal() {
            return val;
        }
        public void setVal(int val) {
            this.val = val;
        }
        public List<TreeNode> getChildren() {
            return children;
        }
        public void setChildren(List<TreeNode> children) {
            this.children = children;
        }
    }
    
    public static List<List<Integer>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while(queue.size() != 0) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                for (TreeNode child : node.getChildren()) {
                    queue.offer(child);
                }
                level.add(node.val);
            }
            result.add(level);
        }
        return result;
    }
    
//            1
//          / | \
//        2   3   4
//       /|\  |   |
//      5 6 7 8   9
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1, new TreeNode(2, new TreeNode(5), new TreeNode(6), new TreeNode(7)), new TreeNode(3, new TreeNode(8)), new TreeNode(4, new TreeNode(9)));
        List<List<Integer>> result = levelOrderTraversal(root);
        for (List<Integer> list : result) {
            for (Integer i : list) {
                System.out.print(i);
                System.out.print(' ');
            }
            System.out.println();
        }
    }
}