Simple Java solution with LinkedList.


  • 27
    P

    The addFirst() method of LinkedLinked save us from reverse final result.

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    	LinkedList<List<Integer>> list = new LinkedList<List<Integer>>();
    	addLevel(list, 0, root);
    	return list;
    }
    
    private void addLevel(LinkedList<List<Integer>> list, int level, TreeNode node) {
    	if (node == null) return;
    	if (list.size()-1 < level) list.addFirst(new LinkedList<Integer>());
    	list.get(list.size()-1-level).add(node.val);
    	addLevel(list, level+1, node.left);
    	addLevel(list, level+1, node.right);
    }

  • 8
    D

    You'd better use ArrayList as "list" variable, because "list.get(list.size() - 1 - level).add(node.val)" works O(n)


  • 0
    Z

    this is top-bottom


  • 0
    S

    list.addFirst(), or list.add(0, new ArrayList<Integer>()) if use ArrayList will be O(n) .


  • 0

    but list.addFirst() will cost more, if you choose ArrayList


  • 0
    R

    It's trade off between ArrayList.add(0, List) and LinkedList.get(list.size()-1-level). Though both are O(n), the latter cost a bit less than the former, comparing them one to one. However, the former only executes for the leftmost node of each level, while the latter runs for all nodes. Therefore, in case of a complete binary tree, the total cost for former and latter are O(n) and O(n^2), respectively.


  • 0
    X

    I think yours are from top to bottom, you can have a slightly change like this
    private void levelOrder(TreeNode root,LinkedList<List<Integer>> res,int level){
    if(root==null)
    return;
    if(res.size()<=level)
    res.addFirst(new ArrayList<Integer>());
    levelOrder(root.left,res,level+1);
    levelOrder(root.right,res,level+1);
    res.get(res.size()-level-1).add(root.val);
    }


  • 0

    @daniel_de_darik Agree! So for DFS version, maybe using Collections.reverse(result) before return final result is a better idea.


Log in to reply
 

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