4
\$\begingroup\$

Here is my code.

/**
 * 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>> list = new LinkedList<List<Integer>>();
        if (root == null) {
            return list;
        } else {
            Queue<TreeNode> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                int size = q.size();
                LinkedList<Integer> layers = new LinkedList<>();
                while (size != 0) {
                    TreeNode current = q.poll();
                    layers.add(current.val);
                    if (current.left != null) {
                        q.add(current.left);
                    }
                    if (current.right != null) {
                        q.add(current.right);
                    }
                    size--;
                }

                list.add(layers);

            }
        }
        return list;

    }

}

Please let me know if any improvement/correction.

\$\endgroup\$
1
  • \$\begingroup\$ Some vertical space (new lines) to group related code would increase readability. \$\endgroup\$ – Heslacher Feb 16 '16 at 8:08
4
\$\begingroup\$

Nicely done. I especially like how you used the size of the queue to know how many items are there on the level. I have only minor improvement ideas.


You can simplify this declaration:

List<List<Integer>> list = new LinkedList<List<Integer>>();

Using the diamond operator <>, like you already did at other places:

List<List<Integer>> list = new LinkedList<>();

The code is deeply indented. You could reduce the indent level by eliminating the else branch of the outermost condition:

    if (root == null) {
        return list;
    }
    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    // ...

The while loop could be written as a for loop. The benefit is that it will be harder to forget to decrement size.


Lastly, some of the names could be better.

  • Instead of "layers", I propose singular "layer"
  • Instead of "size", I propose "count"
\$\endgroup\$
0
1
\$\begingroup\$

Nice iterative way of solving it. I can also think of a simple recursive way of doing this. In this approach, you simply keep on adding values to the listOfLists based on the level index. Here is the code:

private static List<List<Integer>> getLists(TreeNode root){
    List<List<Integer>> listOfLists = new LinkedList<>();
    if(root == null)
        return listOfLists;
    getListsRec(root,listOfLists,1);
    return listOfLists;
}

private static void getListsRec(TreeNode root, List<List<Integer>> listOfLists, int level) {
    if(root == null)
        return ;
    if(listOfLists.size() < level ){
        List<Integer> list = new LinkedList<>();
        list.add(root.value);
        listOfLists.add(list);
    }
    else{
        List<Integer> list = listOfLists.get(level -1);
        list.add(root.value);
    }
    getListsRec(root.left, listOfLists, level+1);
    getListsRec(root.right, listOfLists, level+1);
}

Edit: This can be improved little bit:-

    private static List<List<Integer>> getLists(TreeNode root){
    List<List<Integer>> listOfLists = new LinkedList<>();
    if(root == null)
        return listOfLists;
    getListsRec(root,listOfLists,1);
    return listOfLists;
}

private static void getListsRec(TreeNode root, List<List<Integer>> listOfLists, int level) {
    if(root == null)
        return ;

    if(listOfLists.size() < level ){
        listOfLists.add(new LinkedList<>());
    }

    listOfLists.get(level -1).add(root.value);

    getListsRec(root.left, listOfLists, level+1);
    getListsRec(root.right, listOfLists, level+1);
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.