填充每个节点的下一个右侧节点指针 II

简介: 填充每个节点的下一个右侧节点指针 II

[填充每个节点的下一个右侧节点指针 II](https://leetcode.cn/problems/populating-

一、题目描述:

给定一个二叉树

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

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

进阶:

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

示例:

img

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

提示:

树中的节点数小于 6000
-100 <= node.val <= 100

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、思路分析:

根节点不为null,将根节点入队。并进入循环。
设置size表示当前层一共有多少个节点。
设置pre结点表示前一个结点。每从队列中出队一个结点,将pre的next指针指向出队结点。
pre结点后移。
判断如果有左右孩子,分别将左右孩子入队。

三、AC 代码:

    public Node connect(Node root) {
        Node tail = root;
        Deque<Node> deque = new ArrayDeque<>();
        if (tail != null) deque.addFirst(tail);
        while (!deque.isEmpty()) {
            int size = deque.size();
            Node pre = null;
            for (int i = 0; i < size; i++) {
                if (pre == null) pre = deque.pollLast();
                else {
                    pre.next = deque.peekLast();
                    pre = deque.pollLast();
                }
                if (pre.left != null) deque.addFirst(pre.left);
                if (pre.right != null) deque.addFirst(pre.right);
            }
        }
        return root;
    }

四、总结:

image.png

掘友们,解题不易,留下个赞或评论再走吧!谢啦~ 💐

希望对你有帮助

期待下次再见~

相关文章
10_填充每个节点的下一个右侧节点指针
10_填充每个节点的下一个右侧节点指针
|
5月前
|
存储 SQL 算法
LeetCode 题目 117:填充每个节点的下一个右侧节点指针 II
LeetCode 题目 117:填充每个节点的下一个右侧节点指针 II
|
5月前
|
存储 SQL 算法
LeetCode 题目 116:填充每个节点的下一个右侧节点指针
LeetCode 题目 116:填充每个节点的下一个右侧节点指针
|
6月前
|
存储 C语言
链表—初始化指针变和创建新的节点------区别应用分析
链表—初始化指针变和创建新的节点------区别应用分析
|
6月前
|
Rust 索引
Rust 编程小技巧摘选(6)
Rust 编程小技巧摘选(6)
82 1
Rust 编程小技巧摘选(6)
力扣117 填充每个节点的下一个右侧节点指针II
力扣117 填充每个节点的下一个右侧节点指针II
|
5月前
|
C语言
指针进阶(C语言终)
指针进阶(C语言终)
|
1月前
|
C语言
无头链表二级指针方式实现(C语言描述)
本文介绍了如何在C语言中使用二级指针实现无头链表,并提供了创建节点、插入、删除、查找、销毁链表等操作的函数实现,以及一个示例程序来演示这些操作。
22 0
|
2月前
|
存储 人工智能 C语言
C语言程序设计核心详解 第八章 指针超详细讲解_指针变量_二维数组指针_指向字符串指针
本文详细讲解了C语言中的指针,包括指针变量的定义与引用、指向数组及字符串的指针变量等。首先介绍了指针变量的基本概念和定义格式,随后通过多个示例展示了如何使用指针变量来操作普通变量、数组和字符串。文章还深入探讨了指向函数的指针变量以及指针数组的概念,并解释了空指针的意义和使用场景。通过丰富的代码示例和图形化展示,帮助读者更好地理解和掌握C语言中的指针知识。
|
3月前
|
C语言
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)
【C初阶——指针5】鹏哥C语言系列文章,基本语法知识全面讲解——指针(5)