您现在的位置是:首页 >技术交流 >LeetCode 117. 填充每个节点的下一个右侧节点指针 II网站首页技术交流
LeetCode 117. 填充每个节点的下一个右侧节点指针 II
简介LeetCode 117. 填充每个节点的下一个右侧节点指针 II
117. 填充每个节点的下一个右侧节点指针 II
描述
给定一个二叉树:
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL 。
初始状态下,所有 next 指针都被设置为 NULL 。
示例
示例1
输入:root = [1,2,3,4,5,null,7]
输出:[1,#,2,3,#,4,5,7,#]
解释:给定二叉树如图 A 所示,你的函数应该填充它的每个 next 指针,以指向其下一个右侧节点,如图 B 所示。序列化输出按层序遍历顺序(由 next 指针连接),‘#’ 表示每层的末尾。
示例2
输入:root = []
输出:[]
链接
https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/
解题思路
思路一: 层次遍历
跟LeetCode 116. 填充每个节点的下一个右侧节点指针解题一模一样。
- 首先根元素入队
- 当队列不为空的时候
- 求当前队列的长度length
- 依次从队列中取 length个元素进行处理, 先取出队列中的第一个节点node,当node不是最后一个时,将node.next指向队列的第一个,然后进入下一次迭代
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if (root == null) return root;
let queue = [root];
while(queue.length) {
let len = queue.length;
for (let i = 0; i < len; i++) {
let node = queue.shift();
if (i < len - 1) {
node.next = queue[0];
}
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root;
};
时间复杂度: O(n), 其中 n 是二叉树的节点数
空间复杂度: O(n)
思路二: 使用哑节点
新建哑结点, 方便把下一层的节点串起来
实现代码如下:
/**
* @param {Node} root
* @return {Node}
*/
var connect = function(root) {
if (root === null) return root;
let cur = root;
while (cur != null) {
// 新建哑结点 方便把下一层的节点串起来
let dummy = new Node(0), prev = dummy;
while (cur != null) {
// 如果当前节点的左子节点不为空,就让pre节点的next指向它
if (cur.left != null) {
prev.next = cur.left;
prev = prev.next;
}
if (cur.right != null) {
prev.next = cur.right;
prev = prev.next;
}
// 指针向后移动
cur = cur.next;
}
// 把下一层串联成一个链表之后,让他赋值给cur,后续继续循环,直到cur为空为止
cur = dummy.next;
}
return root;
}
参考资料
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。