首页 > 编程语言 >【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II

时间:2023-11-04 11:08:32浏览次数:37  
标签:Node 遍历 val int next 117 节点 妹学 public

2哥 : 3妹,听说你昨天去面试了,怎么样啊?
3妹:嗨,别提了,让我回去等通知,估计是没有通知了, 还浪费我请了一天假。
2哥 : 你又请假了啊, 你是怎么跟你那个严厉的老板请假的。
3妹:我说我2哥生病了,嘿嘿~

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II_层次遍历


2哥:一猜就是说我生病了,自从你找工作,我这一年都病了十几回了……
3妹:没办法,假不好请嘛, 我尽快找到工作,让你的病快点好。
2哥:你就不能盼我点好,你可以说你2哥结婚了嘛
3妹:对哦,这个理由可以下次说。 不过2哥,你还是个单身狗耶, 要赶紧给我找个2嫂了哈~
2哥:去去,不跟你说了,再给你出道题,兴许下次面试会遇到:

 1题目: 

给定一个二叉树:

struct Node {
    int val;
    Node *left;
    Node *right;
    Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。

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

示例 1:


【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II_二叉树_02


输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),'#' 表示每层的末尾。
示例 2:

输入:root = []
输出:[]

提示:

树中的节点数在范围 [0, 6000] 内
-100 <= Node.val <= 100
进阶:

你只能使用常量级额外空间。
使用递归解题也符合要求,本题中递归程序的隐式栈空间不计入额外空间复杂度。

 2思路: 

【教3妹学编程-算法题】117. 填充每个节点的下一个右侧节点指针 II_层次遍历_03

层次遍历。树的层次遍历基于广度优先搜索,它按照层的顺序遍历二叉树,在遍历第 i层前,一定会遍历完第 i−1 层。

算法如下:初始化一个队列 q,将根结点放入队列中。当队列不为空的时候,记录当前队列大小为 n,从队列中以此取出 n 个元素并通过这 n 个元素拓展新节点。如此循环,直到队列为空。

 3java代码: 

/*
// 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 null;
        }
        Queue<Node> queue = new ArrayDeque<Node>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int n = queue.size();
            Node last = null;
            for (int i = 1; i <= n; ++i) {
                Node f = queue.poll();
                if (f.left != null) {
                    queue.offer(f.left);
                }
                if (f.right != null) {
                    queue.offer(f.right);
                }
                if (i != 1) {
                    last.next = f;
                }
                last = f;
            }
        }
        return root;
    }
}

标签:Node,遍历,val,int,next,117,节点,妹学,public
From: https://blog.51cto.com/u_6813689/8179124

相关文章

  • 教3妹学编程-算法题】2914. 使二进制字符串变美丽的最少修改次数
    3妹:呜呜,烦死了,脸上长了一个痘2哥 :不要在意这些细节嘛,不用管它,过两天自然不就好了。3妹:切,你不懂,影响这两天的心情哇。2哥 :我看你是不急着找工作了啊,工作那么辛苦,哪还有时间想这些啊。3妹:说到找工作,我又要去刷题了。2哥:我给你出一道关于美丽的题吧,让你的心情美丽美丽~ 1题目......
  • 【教3妹学编程-算法题】数组中两个数的最大异或值
    3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”2哥 :3妹,什么事呀这么开心呀。3妹:2哥你看今天的天气多好啊,阳光明媚、万里无云、秋高气爽,适合秋游。2哥:是啊,都快立冬了,天气还是这么热。今年的冬天比以往来的要晚一些。3妹:晚来也是要来的,看天气预报下周要降温,估计没几......
  • 11月LeetCode每日一题: 117. 填充每个节点的下一个右侧节点指针 II
    题目描述:给定一个二叉树:structNode{intval;Node*left;Node*right;Node*next;}填充它的每个next指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将next指针设置为 NULL 。初始状态下,所有 next指针都被设置为 NULL 。 考察......
  • 记一次GFS集群节点系统重做数据恢复
    背景:比较倒霉,周日晚上服务器硬盘损坏更换后发现数据块损坏,系统无法正常使用只能重做系统,恢复了好多虚拟机,过程无比痛苦,目前只说一说恢复gfs。思路:登录gfs master节点查看peer状态,glusterpeerstatus  发现另一个节点处于State:PeerRejected(Disconnected)先把peer点......
  • 倾斜摄影三维模型的根节点合并的文件大小与质量关系分析
    倾斜摄影三维模型的根节点合并的文件大小与质量关系分析 倾斜摄影三维模型的根节点合并过程涉及大量的数据,包括高分辨率图像和点云信息。在进行根节点合并时,文件大小和质量之间存在一定的关系。本文将分析倾斜摄影三维模型的根节点合并的文件大小与质量之间的关系。首先,文件......
  • 寻找两个链表相交节点方法(可以是有环链表)
    问题分析:两个链表相交可以分为两个大类,一是两个无环链表相交,二是两个有环链表相交。 无环相交如图:有环相交有两种情况,一种是先相交后成环,如图:另一种是交点有两个,是成环后的交点(入环节点不同) 方法1.判断链表是否有环,返回第一个入环节点。2.判断是否相交3.......
  • 前端歌谣的刷题之路-第六十八题-js动态创建节点
     前言我是歌谣我有个兄弟巅峰的时候排名c站总榜19叫前端小歌谣曾经我花了三年的时间创作了他现在我要用五年的时间超越他今天又是接近兄弟的一天人生难免坎坷大不了从头再来歌谣的意志是永恒的放弃很容易但是坚持一定很酷本题目源自于牛客网微信公众号前端小歌谣题目......
  • 验证2个节点udp和tcp可通性
    -u表示udp,默认是tcp。-l表示作为server监听。server:192.168.0.104上开启udp123端口server发送11client:连接192.168.0.104上udp123端口client发送100 server:192.168.0.104上开启tcp123端口server发送102client:连接192.168.0.104上tcp123端口client发送101......
  • Databend 开源周报第 117 期
    Databend是一款现代云数仓。专为弹性和高效设计,为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务:https://app.databend.cn。What'sOnInDatabend探索Databend本周新进展,遇到更贴近你心意的Databend。特性预览:只读式ATTACHTABLE为了少数几条大规模查询,而......
  • Databend 开源周报第 117 期
    Databend是一款现代云数仓。专为弹性和高效设计,为您的大规模分析需求保驾护航。自由且开源。即刻体验云服务:https://app.databend.cn。What'sOnInDatabend探索Databend本周新进展,遇到更贴近你心意的Databend。特性预览:只读式ATTACHTABLE为了少数几条大规模查询,......