BFS using 2 queues and one stack


  • 0
    S
    /**
     * 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>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> list = new ArrayList<List<Integer>>();
            List<List<Integer>> list4 = new ArrayList<List<Integer>>();
            if(root==null) return list;
            
            Queue<TreeNode> q1 = new LinkedList<>();
            Queue<TreeNode> q2 = new LinkedList<>();
            Stack<List<Integer>> st = new Stack<List<Integer>>();
            
            q1.add(root);
            while(!q1.isEmpty() || !q2.isEmpty()){
                List<Integer> list1 = new ArrayList<Integer>();
                List<Integer> list2 = new ArrayList<Integer>();
                
                while(!q1.isEmpty()){
                    
                    TreeNode node1 = q1.poll();
                    list1.add(node1.val);
                    if(node1.left!=null) q2.add(node1.left);
                    if(node1.right!=null) q2.add(node1.right);
                }
                //System.out.println(list1);
                if(!list1.isEmpty()) list.add(list1);
                
                while(!q2.isEmpty()){
                    
                    TreeNode node2 = q2.poll();
                    list2.add(node2.val);
                     if(node2.left!=null) q1.add(node2.left);
                    if(node2.right!=null) q1.add(node2.right);
                }
                //System.out.println(list2);
                if(!list2.isEmpty()) list.add(list2);
            }
            
            for(List<Integer> list3:list) {
                st.push(list3);
            }
            
            while(!st.isEmpty()){
                list4.add(st.pop());
            }
            
            return list4;
        }
    }
    

Log in to reply
 

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