My DFS and BFS java solution


  • 116
    S

    DFS solution:

    public class Solution {
        public List<List<Integer>> levelOrderBottom(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            List<List<Integer>> wrapList = new LinkedList<List<Integer>>();
            
            if(root == null) return wrapList;
            
            queue.offer(root);
            while(!queue.isEmpty()){
                int levelNum = queue.size();
                List<Integer> subList = new LinkedList<Integer>();
                for(int i=0; i<levelNum; i++) {
                    if(queue.peek().left != null) queue.offer(queue.peek().left);
                    if(queue.peek().right != null) queue.offer(queue.peek().right);
                    subList.add(queue.poll().val);
                }
                wrapList.add(0, subList);
            }
            return wrapList;
        }
    }
    

    BFS solution:

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

  • 66

    Nice solutions, but the first should be bfs, right?


  • 7
    S

    yes, I mismatch the two solutions' names


  • 2
    C

    Agree, the first is BFD and the second is DFS.


  • 0
    Q

    So the dfs solution actually take O(N^2) runtime.


  • 2
    H

    what a beautiful code...thanks a lot!!!


  • 0
    E

    are you sure that LinkedList has a isEmpty() method??


  • 2

    +1 for confidence.


  • 1
    J

    LinkedList implements interface queue.so it has.


  • 0
    J

    in DFS.line :list.get(list.size()-level-1).add(root.val);i debug:after run it.is levelMaker(list, root.right, level+1); why and the root is changed


  • 1
    T

    Nice solution.


  • 5
    J

    Nice solution. However, add something at the first position of ArrayList also takes long time. It will change all the other indexes.


  • 1

    It seems DFS is much faster, why is that?


  • 1
    W

    said in My DFS and BFS java solution:

    List<List<Integer>> wrapList = new LinkedList<List<Integer>>();

    Just curious: why the line List<List<Integer>> wrapList = new LinkedList<List<Integer>>(); used as like this: List<List<Integer>> wrapList = new Tree<List<Integer>>(); if we have a tree structure.

    I know Tree structure can not be written like this, but why should it be a linkedlist?


  • 4

    @whoppers Tree is neither a valid Java interface, nor a valid implementation.


  • 0

    Awesome Solution


  • 0

    Nice DFS solution! I thought it's not possible but you made it!


  • 0
    R

    Can anyone give a slightly detailed explanation of the DFS solution? (Also, in the BFS, the data structure i.e. linked list or array list automatically accommodates the incoming list in index 0 and shifts others to the right by one, right?) Thanks!


  • 2

    @root_010 I believe you're concerned about the arrangement of lists of node's value. add(index, E), in which the index is zero, will insert the incoming List at the top of the wrapper List. SInce the nature of linkedlist, a new node will be created and points to the current head, meaning no shift of rest lists is necessary.

    Additionally, in DFS solution, "list.get(list.size()-level-1).add(root.val);" will retrieve the list of corresponding level and add its value, when it's been visited.


  • 0
    X

    Can anyone tell me why use add(index, E) is correct but use addFirst(E) is wrong?


Log in to reply
 

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