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

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

 👊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。由此可见层序遍历之强大,是我们必须要掌握的技能之一。同时建议大家一定要自己每次重新手敲而不要去复制粘贴,以加深自己的印象和理解能力。当然每道题的做法也很多,大家也应该去学习一下更加优秀的做法。

相关文章
|
人工智能 算法 BI
LeetCode-390 消除游戏
LeetCode-390 消除游戏
Leetcode 623. Add One Row to Tree
题目很简单,在树的第d层加一层,值为v。递归增加一层就好了。代码如下
110 0
LeetCode 390. Elimination Game
给定一个从1 到 n 排序的整数列表。 首先,从左到右,从第一个数字开始,每隔一个数字进行删除,直到列表的末尾。 第二步,在剩下的数字中,从右到左,从倒数第一个数字开始,每隔一个数字进行删除,直到列表开头。 我们不断重复这两步,从左到右和从右到左交替进行,直到只剩下一个数字。 返回长度为 n 的列表中,最后剩下的数字。
244 0
LeetCode 390. Elimination Game
|
14天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
5天前
|
云安全 人工智能 安全
Dify平台集成阿里云AI安全护栏,构建AI Runtime安全防线
阿里云 AI 安全护栏加入Dify平台,打造可信赖的 AI
|
8天前
|
人工智能 运维 Java
Spring AI Alibaba Admin 开源!以数据为中心的 Agent 开发平台
Spring AI Alibaba Admin 正式发布!一站式实现 Prompt 管理、动态热更新、评测集构建、自动化评估与全链路可观测,助力企业高效构建可信赖的 AI Agent 应用。开源共建,现已上线!
812 27