Java BFS solution together with Stack


  • 4
    Z

    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        List<List<Integer>> level_nodes = new ArrayList<List<Integer>>();
        
        if(root==null){
            return level_nodes;
        }
        
        Stack<List<Integer>> buffer = new Stack<List<Integer>>(); //Because we want a reversed output
    
        Queue<TreeNode> nodes = new LinkedList<TreeNode>();
        nodes.add(root);
        
        while(nodes.size()!=0){
    
            int level_length = nodes.size();
            List<Integer> vals = new ArrayList<Integer>();
    
            while(level_length!=0){
                TreeNode temp = nodes.poll();
    
                if(temp.left!=null)nodes.add(temp.left);
                if(temp.right!=null)nodes.add(temp.right);
    
                vals.add(temp.val);
                level_length--;
            }
    
            buffer.push(vals);
        }
        
        while(!buffer.empty()){
            level_nodes.add(buffer.pop());
        }
        
        return level_nodes;
        
    }

  • 0
    J

    Same idea, but mine is a little bit trivial.

    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Stack<LinkedList<TreeNode>> stack = createLevelLinkedList(root);
            while (!stack.isEmpty()) {
                LinkedList<TreeNode> nodeSubList = stack.pop();
                List<Integer> intSubList = new LinkedList<Integer>();
                for (TreeNode n : nodeSubList) {
                    intSubList.add(n.val);
                }
                result.add(intSubList);
            }
            return result;
        }
        
        private Stack<LinkedList<TreeNode>> createLevelLinkedList(TreeNode root) {
            Stack<LinkedList<TreeNode>> stack = new Stack<LinkedList<TreeNode>>();
            LinkedList<TreeNode> current = new LinkedList<TreeNode>();
            if (root != null)
                current.add(root);
            while(!current.isEmpty()) {
                stack.add(current);
                LinkedList<TreeNode> previous = current;
                current = new LinkedList<TreeNode>();
                for (TreeNode n : previous) {
                    if (n.left != null)
                        current.add(n.left);
                    if (n.right != null)
                        current.add(n.right);
                        
                }
            }
            return stack;
        }
    }

Log in to reply
 

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