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]
]

1. One Queue Solution — Better

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    //one queue
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    Queue<TreeNode> q = new LinkedList<TreeNode>();
    if (root != null) {
        q.offer(root);
    }
    while (!q.isEmpty()) {
        ArrayList<Integer> levelNodes = new ArrayList<>();
        int size = q.size(); //this is the # of nodes in current level
        for (int i = 0; i < size; i++) {
            TreeNode curr = q.poll();
            levelNodes.add(curr.val);
            if (curr.left != null) {
                q.offer(curr.left);
            }
            if (curr.right != null) {
                q.offer(curr.right);
            }
        }
        result.add(levelNodes);
    }
    return result;
}

2. Two Queues Solution — Easier to Understand

public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> output= new ArrayList<ArrayList<Integer>>();
        if(root==null){
            return output;
        }
        ArrayList<TreeNode> current = new ArrayList<TreeNode>();
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        current.add(root);
        while(current.size()!=0){
            children = new ArrayList<TreeNode>();
            ArrayList<Integer> levelNodes= new ArrayList<Integer>();
            for(TreeNode t : current){
                levelNodes.add(t.val);
                if(t.left!=null){
                    children.add(t.left);
                }
                if(t.right!=null){
                    children.add(t.right);
                }
            }
            output.add(levelNodes);
            current = children;
        }
        return output;
    }

Share