LeetCode Notes_#116_填充每个节点的下一个右侧节点指针
Contents
题目
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
示例：
提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
思路分析
方法1：层序遍历
在普通的层序遍历代码基础上进行修改，可以解决本题。但是需要借助的辅助队列空间为O(n),不符合题目要求，仅作为参考。
方法2：借助已有的next指针
分析可知，可以分为两种连接类型：
- 第一类连接：两个节点有相同父节点
- 设节点2是head,可以通过如下代码连接：
head.left.next = head.right
- 第二类连接：两个节点没有相同父节点
- 设节点2是head,可以通过如下代码连接：
if(head.next != null) head.right.next = head.next.left;
这样一来，可以利用当前层的next指针，把下一层的节点连接起来。可以将每一层的遍历过程看作链表的遍历，这是内层循环。
外层循环应该是从上到下遍历每一层，维护一个leftmost指针，指向每一层的最左侧节点。
方法3：递归
参考如下图解，整体思路：
- 将一个树分解为左子树和右子树，每次连接左子树和右子树的相邻部分（只连接左子树和右子树相邻的节点，而不连接左子树和右子树内部的节点）
- 继续将左子树分解为左子树的左子树，左子树的右子树，连接相邻部分。右子树同理。
- ...
这是一个递归过程。
解答
解答1：层序遍历
在普通的层序遍历代码基础上进行修改，可以解决本题。但是需要借助的辅助队列空间为O(n),不符合题目要求，仅作为参考。
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Queue<Node> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
int size = queue.size();
//遍历当前层所有元素，将他们连接起来，并将他们的子节点顺序入队
for(int i = 0;i <= size - 1;i++){
//如果用remove()，则会抛出异常
Node node = queue.poll();
//这里不能用poll(),否则会跳过一个节点，没有访问到
//必须加入条件判断，否则当前层最后节点会连接到下一层
if(i <= size - 2) node.next = queue.peek();
if(node.left != null) queue.offer(node.left);
if(node.right != null) queue.offer(node.right);
}
}
return root;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(n)
解答2：利用已有的next指针
class Solution {
public Node connect(Node root) {
if(root == null) return null;
Node leftmost = root;
//注意：在当前层连接的是下一层的节点
//如果下一层最左侧节点为null,说明已经连接了所有层的节点，可以终止循环
while(leftmost.left != null){
//把当前层节点当成链表，向后遍历
Node head = leftmost;
while(head != null){
//第一种连接（具有相同父节点）
head.left.next = head.right;
//第二种连接（不具有相同父节点）
if(head.next != null) head.right.next = head.next.left;
//链表指针后移
head = head.next;
}
//继续连接下一层
leftmost = leftmost.left;
}
return root;
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)
解答3：递归
class Solution {
public Node connect(Node root) {
dfs(root);
return root;
}
void dfs(Node root){
if(root == null) return;
Node left = root.left;
Node right = root.right;
//以下是最核心的代码，即连接root左右子树，参考图解
while(left != null){
left.next = right;
left = left.right;
right = right.left;
}
dfs(root.left);
dfs(root.right);
}
}复杂度分析
时间复杂度：O(n)
空间复杂度：O(h)，h是树的深度