脚本宝典收集整理的这篇文章主要介绍了116. 填充每个节点的下一个右侧节点指针,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
给定一个 完美二叉树 ,其所有叶子节点都在同一层,每个父节点都有两个子节点。二叉树定义如下:
struct Node { int val; Node *left; Node *right; Node *next; } 填充它的每个 next 指针,让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点,则将 next 指针设置为 NULL。
初始状态下,所有 next 指针都被设置为 NULL。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public Node connect(Node root) {
if (root == null) {
return null;
}
Node cur = root, tail = root;
int size = 1;
while (cur != null) {
Node pre = null;
for (int i = 1; i <= size; ++i) {
if (cur.left != null) {
tail.next = cur.left;
tail = cur.left;
}
if (cur.right != null) {
tail.next = cur.right;
tail = cur.right;
}
if (pre != null) {
pre.next = cur;
}
pre = cur;
cur = cur.next;
}
pre.next = null;
size <<= 1;
}
return root;
}
}
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 root;
}
// 从根节点开始
Node leftmost = root;
while (leftmost.left != null) {
// 遍历这一层节点组织成的链表,为下一层的节点更新 next 指针
Node head = leftmost;
while (head != null) {
// CONNECTION 1
head.left.next = head.right;
// CONNECTION 2
if (head.next != null) {
head.right.next = head.next.left;
}
// 指针向后移动
head = head.next;
}
// 去下一层的最左的节点
leftmost = leftmost.left;
}
return root;
}
}
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;
}
}
以上是脚本宝典为你收集整理的116. 填充每个节点的下一个右侧节点指针全部内容,希望文章能够帮你解决116. 填充每个节点的下一个右侧节点指针所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。