Two Java Solutions, Recursive and Iterative


  • 0
    
    	public List<List<Integer>> levelOrderBottomV1(TreeNode root) {
    		List<List<Integer>> result = new ArrayList<>();
    		List<TreeNode> parentLevel = new ArrayList<>();
    		List<TreeNode> thisLevel = new ArrayList<>();
    		if (root != null)
    			parentLevel.add(root);
    		while (!parentLevel.isEmpty()) {
    			thisLevel.clear();
    			List<Integer> valueList = new ArrayList<>();
    			for (TreeNode node : parentLevel) {
    				if (node != null) {
    					valueList.add(node.val);
    					if (node.left != null)
    						thisLevel.add(node.left);
    					if (node.right != null)
    						thisLevel.add(node.right);
    				}
    			}
    			parentLevel.clear();
    			parentLevel.addAll(thisLevel);
    			result.add(0, valueList);
    		}
    		return result;
    	}
    
    	public List<List<Integer>> levelOrderBottomV2(TreeNode root) {
    		List<List<Integer>> result = new ArrayList<>();
    		treeWalkThrough(result, root, 1);
    		Collections.reverse(result);
    		return result;
    	}
    
    	private void treeWalkThrough(List<List<Integer>> result, TreeNode node, int depth) {
    		if (node != null) {
    			if (result.size() < depth) // it is the first node of this level
    				result.add(new ArrayList<>());
    
    			result.get(depth - 1).add(node.val);
    
    			depth++;
    			treeWalkThrough(result, node.left, depth);
    			treeWalkThrough(result, node.right, depth);
    		}
    	}
    

  • 0
    M

    In my opinion, if we insert something in an ArrayList at some specific index, there will be a lot of time overhead. As we need to move the elements and then insert. I am referring to this line:

    result.add(0,  valueList);
    

  • 0

    @mandalapusc.edu Oh thanks, therefore a LinkedList is preferable here


  • 0
    M

    @keZhenxu There many ways to do this, IMO using LinkedList is one of the good options.


Log in to reply
 

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