# 题目

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

```输入：{"\$id":"1","left":{"\$id":"2","left":{"\$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"\$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"\$id":"5","left":{"\$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"\$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

# 题解

## 方法一: 层序遍历

```class Solution {
public Node connect(Node root) {
if (root == null) return null;
while (!queue.isEmpty()) {
int size = queue.size();
Node current = null;
while (size > 0) {
Node node = queue.poll();
node.next = current;
current = node;
size--;
}
}
return root;
}
}```

## 方法二：递归

• 左右子树分别连起来

• node == null, 直接返回
• node.left != null, 把left.next连到node.right
• node.right != null && node.next != null, 把node的right 连到 node.next的left。例如遍历到2这个节点,把5连接到6.

```class Solution {
public Node connect(Node root) {
// o(1) space.
if (root == null) return null;
if (root.left != null) root.left.next = root.right;
if (root.right != null && root.next != null) root.right.next = root.next.left;
connect(root.left);
connect(root.right);
return root;
}
}```

## 方法三: 层序遍历 o(1)空间复杂度

```class Solution {
public Node connect(Node root) {
Node dummy = new Node(0);
Node pre = dummy;
Node currentRoot = root;
while (currentRoot != null) {
if (currentRoot.left != null) {
pre.next = currentRoot.left;
pre = pre.next;
}
if (currentRoot.right != null) {
pre.next = currentRoot.right;
pre = pre.next;
}
currentRoot = currentRoot.next;
if (currentRoot == null) {
// 切换层.
pre = dummy;
currentRoot = dummy.next;
dummy.next      = null;
}
}
return root;
}
}```

75 篇文章15 人订阅

0 条评论