还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)(下)

简介: 还不知道层序遍历有多强?带你一口气打穿十道题(动图理解)

 👊7.填充每个节点的下一个右侧节点指针


给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:


填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。


初始状态下,所有 next 指针都被设置为 NULL。


题目链接:填充每个节点的下一个右侧节点指针https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/


       这道题稍难与前面的几道题,不过也不难看出是层序遍历的思想,只不过我们需要每次保存住上一个遍历的结点,然后去让它的next属性指向当前结点,大家通过代码即可理解。


class Solution {
    public Node connect(Node root) {
        dfs(root);
        return root;
    }
    public void dfs(Node root){
        if(root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node a=queue.poll();
            int len=queue.size();
            if(a.left!=null) queue.offer(a.left);
            if(a.right!=null) queue.offer(a.right);
            while(len>0){
                Node b=queue.poll();
                if(b.left!=null) queue.offer(b.left);
                if(b.right!=null) queue.offer(b.right);
                a.next=b;
                a=a.next;
                len--;
            }
        }       
    }
}


👊8.填充每个节点的下一个右侧节点指针||


给定一个二叉树(上一题是完美)


struct Node {

 int val;

 Node *left;

 Node *right;

 Node *next;

}

填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。


初始状态下,所有 next 指针都被设置为 NULL。


题目链接:填充每个节点的下一个右侧节点指针||https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/


         这道题和上一道题唯一的区别就是上题是给的完美二叉树,这道题给的是非完美的二叉树。但是!有区别吗?根本不影响我们上一道题的代码实现,同样的代码同样适用


       广度优先搜索做法(层序遍历)


class Solution {
    public Node connect(Node root) {
        dfs(root);
        return root;
    }
    public void dfs(Node root){
        if(root==null) return;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            Node a=queue.poll();
            int len=queue.size();
            if(a.left!=null) queue.offer(a.left);
            if(a.right!=null) queue.offer(a.right);
            while(len>0){
                Node b=queue.poll();
                if(b.left!=null) queue.offer(b.left);
                if(b.right!=null) queue.offer(b.right);
                a.next=b;
                a=a.next;
                len--;
            }
        }       
    }
}

       题解区中一个非常优秀的递归做法:


class Solution {
    Map<Integer, Node> map = new HashMap<>();
    public Node connect(Node root) {
        helper(root, 0);
        return root;
    }
    void helper(Node node, int deepth){
        if(node == null) return;
        if(map.containsKey(deepth)){
            map.get(deepth).next = node;
        }
        map.put(deepth, node);
        helper(node.left, deepth + 1);
        helper(node.right, deepth + 1);
    }
}


👊9.二叉树的最大深度


给定一个二叉树,找出其最大深度。


二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。


说明: 叶子节点是指没有子节点的节点。


题目链接:二叉树的最大深度https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/


       这道题其实用深度优先搜索的递归做法是最简单的。但利用广搜的层序遍历同样非常容易理解。  while(!queue.isEmpty())循环每次进入一次都代表着会进入新的一层去遍历,我们只需要去统计进入了多少次第一个whille循环即可。


      层序遍历模板做法:


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

        深搜的递归做法:


class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }
}


👊10.二叉树的最小深度


给定一个二叉树,找出其最小深度。


最小深度是从根节点到最近叶子节点的最短路径上的节点数量。


说明:叶子节点是指没有子节点的节点。


题目链接:二叉树的最小深度https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/


         这道题同上,利用深度优先搜索的递归做法是最简单的。但同样我们这里利用层序遍历去做,如果能知道一个结点是叶子结点呢?当然是它没有左子节点和右子结点的时候,我们同样每次像上一题一样去记录进入循环的次数,当判断到某个结点是子结点,说明该结点所在层的深度就是最小深度


class Solution {
    int min=Integer.MAX_VALUE;
    public int minDepth(TreeNode root) {
        bfs(root);
        return min==Integer.MAX_VALUE?0:min;
    }
    void bfs(TreeNode root){
        if(root==null) return;
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int ans=0;
        while(!queue.isEmpty()){
            int len=queue.size();
            ans++;
            while(len-->0){
                TreeNode x=queue.poll();
                if(x.left==null&&x.right==null) min=Math.min(ans,min);
                if(x.left!=null) queue.offer(x.left);
                if(x.right!=null) queue.offer(x.right);
            }
        }
    }
}

      深度优先搜索的递归做法


class Solution {
    public int minDepth(TreeNode root) {
        if(root==null) return 0;
        if(root.left==null&&root.right==null) return 1;
        if(root.left==null) return minDepth(root.right)+1;
        if(root.right==null) return minDepth(root.left)+1;
        return Math.min(minDepth(root.left),minDepth(root.right))+1;
    }
}


🍓3.胜利感谢


        可以发现这十道题用上层序遍历后,大部分题只需要在一个模板代码进行稍微地改动即可AC。由此可见层序遍历之强大,是我们必须要掌握的技能之一。同时建议大家一定要自己每次重新手敲而不要去复制粘贴,以加深自己的印象和理解能力。当然每道题的做法也很多,大家也应该去学习一下更加优秀的做法。

相关文章
|
7天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
6天前
|
存储 人工智能 Java
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
本文讲解 Prompt 基本概念与 10 个优化技巧,结合学术分析 AI 应用的需求分析、设计方案,介绍 Spring AI 中 ChatClient 及 Advisors 的使用。
314 130
AI 超级智能体全栈项目阶段二:Prompt 优化技巧与学术分析 AI 应用开发实现上下文联系多轮对话
|
18天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1328 8
|
5天前
|
监控 JavaScript Java
基于大模型技术的反欺诈知识问答系统
随着互联网与金融科技发展,网络欺诈频发,构建高效反欺诈平台成为迫切需求。本文基于Java、Vue.js、Spring Boot与MySQL技术,设计实现集欺诈识别、宣传教育、用户互动于一体的反欺诈系统,提升公众防范意识,助力企业合规与用户权益保护。
|
17天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1407 87
|
6天前
|
人工智能 Java API
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
本文介绍AI大模型的核心概念、分类及开发者学习路径,重点讲解如何选择与接入大模型。项目基于Spring Boot,使用阿里云灵积模型(Qwen-Plus),对比SDK、HTTP、Spring AI和LangChain4j四种接入方式,助力开发者高效构建AI应用。
312 122
AI 超级智能体全栈项目阶段一:AI大模型概述、选型、项目初始化以及基于阿里云灵积模型 Qwen-Plus实现模型接入四种方式(SDK/HTTP/SpringAI/langchain4j)
|
5天前
|
JavaScript Java 大数据
基于JavaWeb的销售管理系统设计系统
本系统基于Java、MySQL、Spring Boot与Vue.js技术,构建高效、可扩展的销售管理平台,实现客户、订单、数据可视化等全流程自动化管理,提升企业运营效率与决策能力。
|
6天前
|
弹性计算 安全 数据安全/隐私保护
2025年阿里云域名备案流程(新手图文详细流程)
本文图文详解阿里云账号注册、服务器租赁、域名购买及备案全流程,涵盖企业实名认证、信息模板创建、域名备案提交与管局审核等关键步骤,助您快速完成网站上线前的准备工作。
251 82
2025年阿里云域名备案流程(新手图文详细流程)