填充每个节点的下一个右侧节点指针
给定一个 完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
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 指针连接，'#' 标志着每一层的结束。
方法一：层次遍历
public Node connect(Node root) {
if (root == null) {
return root;
}
Node res = root;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
root = queue.poll();
if (i < size - 1) {
root.next = queue.peek();
}
if (root.left != null) {
queue.offer(root.left);
}
if (root.right != null) {
queue.offer(root.right);
}
}
}
return res;
}
方法二：使用已建立的next指针
第一种 是这两个串联的节点都有一个共同的父节点，通过父节点就可以将这两个子节点串联起来
roo.left.next => root.right
第二种 是这两个串联的节点的父节点不同，对于这种情况，如果我们能将这一层的上一层串联好。那么可以通过父节点的next找到邻居，完成串联。
root.right.next => root.next.left这里我们需要保证 root.next 不为空就可以了。
也就是说当我们要串联第 i 层节点时，需要先完成第 i-1 层的节点串联
第一层最多只有一个节点，不需要串联
第二层最多只有两个节点，借助根节点就可以完成串联了
第三层串联时，上一层已经串联完了，所以第三层可以完成串联
同理，可以完成第四层，第五层，第N层的串联
public Node connect(Node root) {
if (root == null) {
return root;
}
Node head = root;
while (head.left != null) {
Node p = head;
while (p != null) {
p.left.next = p.right;
if (p.next != null) {
p.right.next = p.next.left;
}
p = p.next;
}
head = head.left;
}
return root;
}
方法三：递归
public Node connect(Node root) {
if (root == null) {
return null;
}
if (root.left != null) {
root.left.next = root.right;
if (root.next != null) {
root.right.next = root.next.left;
}
connect(root.left);
connect(root.right);
}
return root;
}
填充每个节点的下一个右侧节点指针 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 指针连接），'#' 表示每层的末尾。
使用已建立的 next 指针
- 从第一层开始（第一层只有一个 root 节点），每次循环遍历当前层的链表节点，通过节点的 left 和 right 得到下一层的节点。
- 把下一层的节点从左到右连接成一个链表。
- 拿到下一层链表的头节点，进入下一轮循环。
代码实现时，可以用一个哨兵节点来表示「第一个节点之前的节点」，从而减少一些关于空节点的判断逻辑。
public Node connect(Node root) {
if (root == null) {
return root;
}
Node dummy = new Node();
Node p = root;
while (p != null) {
Node q = dummy;
while (p != null) {
if (p.left != null) {
q.next = p.left;
q = q.next;
}
if (p.right != null) {
q.next = p.right;
q = q.next;
}
p = p.next;
}
p = dummy.next;
dummy.next = null;
}
return root;
}
递归
DFS 这棵树，从根节点 1 出发，向左递归到 2，再向左递归到 4。
这三个节点正好是每一层的第一个节点（类似链表头），用一个数组 pre 记录，即 pre[0] 为节点 1，pre[1] 为节点 2，pre[2] 为节点 4。pre的下标就是节点的深度。
继续递归到 5（深度为 2），从 pre[2] 中拿到节点 4，把 4 的 next 指向 5。然后更新 pre[2] 为节点 5，这样在后面递归到节点 7 时，就可以从 pre[2] 中拿到节点 5，把 5 的 next 指向 7 了。
private List<Node> pre = new ArrayList<>();
public Node connect(Node root) {
dfs(root, 0);
return root;
}
private void dfs(Node root, int level) {
if (root == null) {
return;
}
if (level == pre.size()) {
pre.add(root);
} else {
pre.get(level).next = root;
pre.set(level, root);
}
dfs(root.left, level + 1);
dfs(root.right, level + 1);
}
