栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

广度优先搜索遍历二叉树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

广度优先搜索遍历二叉树

1.前言

当我们在需要遍历一棵二叉树时,我们可以使用广度优先搜索算法(BFS)进行实现,广度优先算法会一层一层的遍历二叉树,从根节点向下一层一层的访问,直到没有节点为止。

2. Queue

在Java中,我们一般使用队列(Queue)进行广度优先搜索的实现。
Queue中的主要方法:

  • add()或offer()加入数据
  • poll()从队列中删除第一个元素
  • peek()用于在队列的头部查询元素,只得到但不会删除这个元素,
  • isEmpty()判断当前队列是非为空。
3. 实现思路

创建队列后先将根结点入队,然后开始遍历,先将队首结点可拓展的点入队,如果没有可拓展的点,将队首结点出队。重复以上步骤,直到到达目标位置或者队列为空。

4. 具体问题

LeetCode-965. 单值二叉树:问题就是判断这个二叉树每个结点的值是不是一样,我们来进行实现

    public boolean isUnivalTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        //保存根结点的值
        int val = root.val;
        //创建一个队列进行广度优先搜索
        Queue queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode temp = queue.poll();
            //如果当前结点的值不等于根结点的值,就返回false
            if (temp.val != val) {
                return false;
            }
            if (temp.left != null) {
                queue.add(temp.left);
            }
            if (temp.right != null) {
                queue.add(temp.right);
            }
        }
        //遍历完整个二叉树都没有返回false,说明每个结点的值都一样
        return true;
    }
5. 总结

遇到二叉树遍历的问题就马上想到深度优先搜索来解决。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/930580.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号