一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 514|回复: 6
收起左侧

[算法题] Leetcode 366 有没有好的BFS算法?

[复制链接] |试试Instant~ |关注本帖
littlebearull 发表于 2016-8-16 08:30:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
小伙伴们,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].
muybienw 发表于 2016-8-16 09:18:10 | 显示全部楼层
可以记录每个node的out degree,然后把所有的leaves放到第一层。每次处理好一个leaf,就减去parent node的out degree。degree减为0的放进下一层。不过这样需要额外记录parent和child的关系。

其实把这题想成undirected graph,有点像leetcode 310,minimum height trees
回复 支持 反对

使用道具 举报

forteller 发表于 2016-8-16 16:00:43 | 显示全部楼层
Topological sorting
回复 支持 反对

使用道具 举报

annawuyi 发表于 2016-8-16 18:45:16 | 显示全部楼层
请问楼主leetcode 现在有多少题了?谢谢
回复 支持 反对

使用道具 举报

 楼主| littlebearull 发表于 2016-8-16 23:10:10 | 显示全部楼层
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;
    }
回复 支持 反对

使用道具 举报

 楼主| littlebearull 发表于 2016-8-16 23:11:03 | 显示全部楼层

谢谢回复!我已经按照topological sorting写了以下代码,如果您发下我的代码有可以优化的地方,麻烦告知以下哦~多谢多谢!共同进步!:)
回复 支持 反对

使用道具 举报

 楼主| littlebearull 发表于 2016-8-16 23:11:59 | 显示全部楼层
annawuyi 发表于 2016-8-16 18:45
请问楼主leetcode 现在有多少题了?谢谢

今天看了以下,已经有385道题了~~ 这出新题的速度太快了,:(
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 01:11

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表