当前位置： 首页 > article >正文

【算法系列-二叉树】层序遍历

article 2024/10/30 19:25:16

【算法系列-二叉树】层序遍历

文章目录

  • 【算法系列-二叉树】层序遍历
    • 1. 算法分析🛸
    • 2. 相似题型🎯
      • 2.1 二叉树的层序遍历II(LeetCode 107)
      • 2.2 二叉树的右视图(LeetCode 199)
      • 2.3 二叉树的层平均值(LeetCode 637)
      • 2.4 N叉树的层序遍历(LeetCode 429)
      • 2.5 在每个树行中找最大值(LeetCode 515)
      • 2.6 填充每个节点的下一个右侧节点指针(LeetCode 116)
      • 2.7 二叉树的最大深度(LeetCode 104)
      • 2.8 二叉树的最小深度(LeetCode 111)

1. 算法分析🛸

二叉树的层序遍历就是对树进行广度优先搜索，一层一层的对树的节点进行遍历；

【题目链接】102. 二叉树的层序遍历 - 力扣（LeetCode）

在这里，我们通过队列来辅助实现二叉树的层序遍历，关键在于寻找到判断当前节点正在哪一层且这一层的节点是否遍历完的条件。

解题过程🎬

定义一个size，这个size等于当前队列的长度大小；

开始先将根节点加入队列，形成第一层； 此时size = 1，再将队列中的节点弹出，将该节点的左右节点加入队列(非空)，同时size - 1；

重复上述过程，直到size = 0时，表示当前层数的节点已经遍历完，进入下一层，直到队列为空，返回结果

代码示例🌰

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {

            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}

下面提供一些与层序遍历解法相似的类型题:

2. 相似题型🎯

2.1 二叉树的层序遍历II(LeetCode 107)

【题目链接】107. 二叉树的层序遍历 II - 力扣（LeetCode）

代码示例🌰

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(0, list);
        }
        return ret;
    }
}

2.2 二叉树的右视图(LeetCode 199)

【题目链接】199. 二叉树的右视图 - 力扣（LeetCode）

解题思路与使用队列的层序遍历相同，需要注意的是要找到能够在右视图看到的节点，这个节点可以是左节点也可以是右节点，但它一定是每一层遍历的最右边节点，对此在遍历到队列中size为0的前一个节点时，将这个节点的值加入返回数组即可

代码示例🌰

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 1) {
                queueOfferNode(queue);
                size--;
            }
            TreeNode node = queueOfferNode(queue);
            ret.add(node.val);
        }
        return ret;
    }

    TreeNode queueOfferNode(Queue<TreeNode> queue) {
        TreeNode cur = queue.poll();
        if (cur.left != null) {
            queue.offer(cur.left);
        }
        if (cur.right != null) {
            queue.offer(cur.right);
        }
        return cur;
    }
}

2.3 二叉树的层平均值(LeetCode 637)

【题目链接】637. 二叉树的层平均值 - 力扣（LeetCode）

代码示例🌰

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int num = size;
            double sum = 0;
            while (size > 0) {
                TreeNode cur = queue.poll();
                sum += cur.val;
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(sum / num);
        }
        return ret;
    }
}

2.4 N叉树的层序遍历(LeetCode 429)

【题目链接】429. N 叉树的层序遍历 - 力扣（LeetCode）

代码示例🌰

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                Node cur = queue.poll();
                list.add(cur.val);
                List<Node> children = cur.children;
                for (Node node : children) {
                    if (node != null) {
                        queue.offer(node);
                    }
                }
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
}

2.5 在每个树行中找最大值(LeetCode 515)

【题目链接】515. 在每个树行中找最大值 - 力扣（LeetCode）

代码示例🌰

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            int max = Integer.MIN_VALUE;
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (cur.val > max) {
                    max = cur.val;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
            ret.add(max);
        }
        return ret;
    }
}

2.6 填充每个节点的下一个右侧节点指针(LeetCode 116)

【题目链接】116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

代码示例🌰

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Node cur1 = queue.poll();
                Node cur2 = size == 0 ? null : queue.peek();
                cur1.next = cur2;
                if (cur1.left != null) {
                    queue.offer(cur1.left);
                }
                if (cur1.right != null) {
                    queue.offer(cur1.right);
                }
            }
        }
        return root;
    }
}

2.7 二叉树的最大深度(LeetCode 104)

【题目链接】104. 二叉树的最大深度 - 力扣（LeetCode）

代码示例🌰

class Solution {
    public int maxDepth(TreeNode root) {
        int ret = 0;
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ret++;
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
        }
        return ret;
    }
}

2.8 二叉树的最小深度(LeetCode 111)

【题目链接】111. 二叉树的最小深度 - 力扣（LeetCode）

代码示例🌰

class Solution {
    public int minDepth(TreeNode root) {
        int ret = 0;
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            ret++;
            int size = queue.size();
            while (size > 0) {
                TreeNode cur = queue.poll();
                if (cur.left == null && cur.right == null) {
                    return ret;
                }
                if (cur.left != null) {
                    queue.offer(cur.left);
                }
                if (cur.right != null) {
                    queue.offer(cur.right);
                }
                size--;
            }
        }
        return ret;
    }
}

以上便是对二叉树层序遍历问题的介绍了！！后续还会继续分享其它算法系列内容，如果这些内容对大家有帮助的话请给一个三连关注吧💕( •̀ ω •́ )✧( •̀ ω •́ )✧✨


http://www.kler.cn/a/371951.html

相关文章：

  • 十分钟Linux中的epoll机制
  • YOLO即插即用模块---CAA
  • 股票基础交易规则!最小变动数量规则!最大数量限制规则!
  • （蓝桥杯C/C++）——常用库函数
  • qt配置https请求
  • 采用STM32CubeMX和HAL库的定时器应用实例
  • 【2024|滑坡数据集论文解读1】CAS滑坡数据集：用于深度学习滑坡检测的大规模多传感器数据集
  • Scala 特质（Traits）与类继承 #scala #Scala #Scala继承
  • Mac程序坞窗口预览的方法来了
  • lego-loam featureAssociation 源码注释（七）
  • 使用 Kafka 和 MinIO 实现人工智能数据工作流
  • Windows 上更新OpenSSL 到 1.1.1
  • 现代化可观测性平台（1）
  • C语言常用的数据类型有哪些？
  • uniapp封装movable-area+movable-view组件，实现悬浮按钮可拖动，自动吸附边缘效果，自动向两边靠拢
  • element ui中el-image组件查看图片的坑
  • QT相机连接与拍照
  • 深度学习（七）深度强化学习：融合创新的智能之路（7/10）
  • Python 爬虫项目实战：爬取某云热歌榜歌曲
  • 使用Python来下一场雪
  • STM32F103C8T6 IO 操作
  • DevOps赋能：优化业务价值流的实战策略与路径（下）
  • ViSual studio如何安装 并使用GeographicLib
  • 大模型提示词简介 举例
  • zjy-sqlite-manage使用文档v1
  • 每日读则推(十四)——Meta Movie Gen: the most advanced media foundation models to-date