Accepted BFS and DFS Solutions JAVA


  • 0
    W

    BFS Solution

      public List<List<Integer>> levelOrder(TreeNode root) {
        
        if(root==null) return new ArrayList<List<Integer>>();
    
        ArrayDeque<TreeNode> q = new ArrayDeque<TreeNode>();
    
        q.add(root);
    
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        
        while(!q.isEmpty()) {
            int size = q.size(); //  level size
            List<Integer> list = new ArrayList<Integer>();
            for(int i=0; i < size; i++) { 
                TreeNode node = q.remove();
                list.add(node.val);
                if(node.left != null) {
                    q.add(node.left);
                } 
                if(node.right != null) {
                    q.add(node.right);
                }
            }
            result.add(list);
        }
    
        return result;
     }
    

    DFS Solution

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list  =  new ArrayList<List<Integer>>();
        if( root != null){
            List<Integer> itemList = new ArrayList<Integer>();
            itemList.add(root.val);
            list.add(itemList);
            dfs(root.left, root.right, 1, list);
        }
        
        return list;
    }
    
    public void dfs(TreeNode left, TreeNode right, int level, List<List<Integer>> list){
        if(left == null && right == null) return;
        
        if( list.size() == level){
            list.add(new ArrayList<Integer>());
        }
        
        List<Integer> itemList = new ArrayList<Integer>(list.get(level));
        
        if(left != null) {
            itemList.add(left.val);
            dfs(left.left, left.right, level + 1, list);
        }
        
        if(right != null) {
            itemList.add(right.val);
            dfs(right.left, right.right, level + 1, list);
        }
        
        list.set(level, itemList); 
        
    }

Log in to reply
 

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