☆打卡算法☆LeetCode 116、 填充每个节点的下一个右侧节点指针 算法解析
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定一个完美二叉树,填充它的每个next指针,让这个指针指向其下一个右侧节点。”题目链接:来源:力扣(LeetCode)链接: ...
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定一个完美二叉树,填充它的每个next指针,让这个指针指向其下一个右侧节点。”
题目链接:
来源:力扣(LeetCode)
2、题目描述
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
示例 1:
输入:root = [1,2,3,4,5,6,7]
输出:[1,#,2,3,#,4,5,6,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化的输出按层序遍历排列,同一层节点由 next 指针连接,'#' 标志着每一层的结束。
示例 2:
输入: root = []
输出: []
二、解题
1、思路分析
题目的题意是要求我们将二叉树的每一层节点都连接起来形成一个链表。
因此比较直接的方法就是层次遍历,在层次遍历的过程中,将二叉树的每一层节点取出来遍历并链接。
层次遍历基于广度优先搜索算法,广度优先搜索算法每次会取出一个节点来拓展,而层次遍历会每次将队列中的所有元素都拿出来拓展。
层次遍历可以保证每次从队列中拿出来遍历的元素都是基于同一层的。
2、代码实现
代码参考:
class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}
// 初始化队列同时将第一层节点加入队列中,即根节点
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
// 外层的 while 循环迭代的是层数
while (!queue.isEmpty()) {
// 记录当前队列大小
int size = queue.size();
// 遍历这一层的所有节点
for (int i = 0; i < size; i++) {
// 从队首取出元素
Node node = queue.poll();
// 连接
if (i < size - 1) {
node.next = queue.peek();
}
// 拓展下一层节点
if (node.left != null) {
queue.add(node.left);
}
if (node.right != null) {
queue.add(node.right);
}
}
}
// 返回根节点
return root;
}
}
3、时间复杂度
时间复杂度 : O(N)
每个节点都会被访问一次且只会被访问一次,所以时间复杂度为O(N)。
空间复杂度: O(N)
广度优先遍历算法的复杂度取决于一个层级上的最大元素数量,这种情况下空间复杂度为O(N)。
三、总结
当然这一题还可以使用已经建立的next指针。
在一棵树中,存在两种类型的next指针:
- 连接同一个父节点的两个子节点,可以通过同一个节点访问到。
- 不同父节点的子节点之间建立连接。
如果每个节点有指向父节点的指针,就可以通过该指针找到next节点。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)