My java non-recursive BFS solution using Queue


  • 0
    G
    public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root==null) return res;
        Queue q = new LinkedList<TreeNode>();
        q.offer(root);
        //cnt1 and cnt2 denote the number of nodes in current level and next level
        int cnt1=1,cnt2=0;
        List<Integer> ll=new ArrayList<Integer>();
        while(!q.isEmpty()){
            TreeNode t=(TreeNode)q.poll();
            ll.add(t.val);
            if(cnt1!=0){
                if(t.left!=null) {cnt2++;q.offer(t.left);}
                if(t.right!=null) {cnt2++;q.offer(t.right);}
            }
            cnt1--;
            if(cnt1==0){
                res.add(ll);
                cnt1=cnt2;
                cnt2=0;
                ll=new ArrayList<Integer>();
            }
        }
       Collections.reverse(res);
       return res;
        
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.