116. 填充每个节点的下一个右侧节点指针(116. Populate the next right node pointer for each node)-其他

116. 填充每个节点的下一个右侧节点指针(116. Populate the next right node pointer for each node)

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}

模拟队列

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 指针

// CONNECTION 1

// CONNECTION 2
}

// 指针向后移动
}

// 去下一层的最左的节点
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;
}
}
————————

Given a} perfect binary tree, all leaf nodes are in the same layer, and each parent node has two child nodes. Binary tree is defined as follows:

struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
Fill in each of its next pointers so that this pointer points to its next right node. If the next right node cannot be found, set the next pointer to null.

In the initial state, all} next pointers are set to null.

Source: leetcode

Simulated queue

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;
}
}

Official explanation

class Solution {
public Node connect(Node root) {
if (root == null) {
return root;
}

// 从根节点开始
Node leftmost = root;

while (leftmost.left != null) {

// 遍历这一层节点组织成的链表，为下一层的节点更新 next 指针

// CONNECTION 1

// CONNECTION 2
}

// 指针向后移动
}

// 去下一层的最左的节点
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;
}
}