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 ..........


  • 1
    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) ?


  • 0
    S

    @akanksha.cse Hi, I think the runtime would still be O(n) for the fact that we still only visit each node once.

    And I want to add that I think the space complexity should be O(h), where h is the depth of the tree.

    Please anyone correct me if I'm wrong. Thanks!


  • 0
    S

    Such a brilliant solution! To be more specific than stating it uses DFS, I would like to say that it implements pre-order traversal to realize level-order traversal. Each time we add root.val into the list, and then look at left and right child.

    Thank you!


Log in to reply
 

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