Java Solution using DFS


  • 85
    G

    Nothing special. Just wanna provide a different way from BFS.

    public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            levelHelper(res, root, 0);
            return res;
        }
        
        public void levelHelper(List<List<Integer>> res, TreeNode root, int height) {
            if (root == null) return;
            if (height >= res.size()) {
                res.add(new LinkedList<Integer>());
            }
            res.get(height).add(root.val);
            levelHelper(res, root.left, height+1);
            levelHelper(res, root.right, height+1);
        }

  • 0
    R

    that check of height>=res.size() makes sure extra LinkedList is not added to res!


  • 0
    K

    (root == null) return; --prevents an extra LinkedList from ever being added to res. It is already correct.


  • 1
    S

    My alternative solution with same idea. I still prefer the queue one.

    public class Solution {
    	List<List<Integer>> lst=new ArrayList<List<Integer>>();
        public List<List<Integer>> levelOrder(TreeNode root) {
            travel(root,0);
            return lst;
        }
    
        private void travel(TreeNode node,int level){    	
        	if(node==null) return;
        	addToList(node.val, level);
        	travel(node.left,level+1);
        	travel(node.right,level+1);
        }
    
        private void addToList(int val, int level){
        	List<Integer> levelList;
        	if(level+1>lst.size()){
        	 	levelList=new LinkedList<Integer>();
        	 	lst.add(levelList);	 	
        	}else levelList=lst.get(level);
        	levelList.add(val);   	
        }
    }
    

  • 0
    E

    concise ..........


  • 0
    K

    height ==res.size() is sufficient...


  • 1
    H

    Very nice code. But why it is wrong if I change

    if (height >= res.size()) {
                res.add(new LinkedList<Integer>());
            }
    

    to

    if (height > res.size() - 1) {
                res.add(new LinkedList<Integer>());
            }
    

  • 0
    M

    fantastic recursive solution.


  • 0

    @haoranc No. It should pass with the change.


  • 0
    A

    Will the runtime of this code be O (no of nodes * max # of nodes at any depth) ?


Log in to reply
 

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