Leetcode 366 有没有好的BFS算法？

小伙伴们，leetcode 366有没有BFS的解法呀？在网上找到的都是dfs解法。我想，只要是tree相关的题目，应该都是有BFS和DFS两种解法的。知道BFS解法的，麻烦告诉一声呀~多谢多谢！（ P.S., 半个多月不刷，回头再看题目，竟然有些生疏了，）
附上题目描述：Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.

Example:
Given binary tree
          1
         / \
        2   3
       / \     
      4   5   
Returns [4, 5, 3], [2], [1].

可以记录每个node的out degree，然后把所有的leaves放到第一层。每次处理好一个leaf，就减去parent node的out degree。degree减为0的放进下一层。不过这样需要额外记录parent和child的关系。

其实把这题想成undirected graph，有点像leetcode 310，minimum height trees

Topological sorting

请问楼主leetcode 现在有多少题了？谢谢

muybienw 发表于 2016-8-16 09:18
可以记录每个node的out degree，然后把所有的leaves放到第一层。每次处理好一个leaf，就减去parent node的o ...

多谢您的回复！利用节点的out-degree，确实可以。不过这样的话，相当于遍历2遍，对吧。以下是我写的代码，主要是用两个hashmap分别存每个节点的children，以及它的parent。麻烦您帮忙看一下，还有可以优化的地方吗？这个bfs的运行时间是dfs的2倍呢，：（ 非常感谢！
public List<List<Integer>> findLeaves(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null) return res;
        HashMap<TreeNode,List<TreeNode>> children=new HashMap<>();
        HashMap<TreeNode,TreeNode> parent=new HashMap<>();
        Queue<TreeNode> queue=new LinkedList<>();queue.offer(root);
        //get the parent-children relation
        while(!queue.isEmpty()){
            TreeNode cur=queue.poll();
            if(!children.containsKey(cur)) children.put(cur,new ArrayList<>());
            if(cur.left!=null){
                children.get(cur).add(cur.left);parent.put(cur.left,cur);queue.offer(cur.left);
            }
            if(cur.right!=null){
                children.get(cur).add(cur.right);parent.put(cur.right,cur);queue.offer(cur.right);
            }
        }
        //topological sort
        for(TreeNode cur:children.keySet()){
            if(children.get(cur).isEmpty()) {queue.offer(cur);}
        }
        while(!queue.isEmpty()){
            int size=queue.size();List<Integer> tmp=new ArrayList<>();
            for(int i=0;i<size;i++){
                TreeNode cur=queue.poll();tmp.add(cur.val);
                TreeNode pa=parent.get(cur);
                    if(pa!=null) {
                        children.get(parent.get(cur)).remove(cur);
                               if(children.get(pa).isEmpty())
                                    queue.offer(pa);
                }
            }
            res.add(tmp);
        }
        return res;
    }

forteller 发表于 2016-8-16 16:00
Topological sorting

谢谢回复！我已经按照topological sorting写了以下代码，如果您发下我的代码有可以优化的地方，麻烦告知以下哦~多谢多谢！共同进步！：）

annawuyi 发表于 2016-8-16 18:45
请问楼主leetcode 现在有多少题了？谢谢

今天看了以下，已经有385道题了~~ 这出新题的速度太快了，：（