Binary tree level order traversal

一層一層遍歷所有節點，非遞迴用個 Queue 做就可以了

public List<List<Integer>> levelOrder(TreeNode root) {
    List result = new ArrayList();

    if (root == null) {
        return result;
    }

    Queue<TreeNode> queue = new LinkedList<TreeNode>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        ArrayList<Integer> level = new ArrayList<Integer>();
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode head = queue.poll();
            level.add(head.val);
            if (head.left != null) {
                queue.offer(head.left);
            }
            if (head.right != null) {
                queue.offer(head.right);
            }
        }
        result.add(level);
    }

    return result;
}

遞迴版：

遞迴有個難點是要怎樣去紀錄層的概念？因為遞迴不可能會左邊等右邊做完才繼續

一定是左邊就左到底，右邊做到底，

那我們可以這樣想，就用一個結構紀錄一直左到底的，右邊右到底時再加入依序的左邊即可

所以用一個大的 ArrayList 在對應的每一層加進 val

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> results = new ArrayList<>();

    if (root == null) {
        return results;
    }

    helper(root, 0, results);
    return results;
}

public void helper(TreeNode root, int level, List<List<Integer>> results) {
    if (root == null) {
        return;
    }

    if (level >= results.size()) {
        results.add(new ArrayList<Integer>());
    }

    results.get(level).add(root.val);
    helper(root.left, level + 1, results);
    helper(root.right, level + 1, results);
    return;
}