题目描述
给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下：
struct Node {
int val;
Node *left;
Node *right;
Node *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
相关话题： 树、深度优先搜索 难度： 中等
示例
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。
提示：
- 你只能使用常量级额外空间。
- 使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
-
解法1
刚看到这道题，我想到的是二叉树的层次遍历，通过一个current指针跟踪 next指针的填充进度。
需要注意的是一个边界情况：该节点是该层的第一个节点
每次从队列中弹出一个Node x,current.next指向x完成next的填充，所以弹出的x==begin时自然要特殊处理，因为它的左边没有节点。
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node next;
public Node() {}
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 null;
Node begin = root;
Node end = root;
Node current = root;
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
while(!queue.isEmpty()){
Node x = queue.poll();
if(x == begin){//如果当前节点是该层第一个节点，begin更新为下
//一层的第一个节点，current = x
begin = x.left;
current = x;
}else{//如果不是第一个节点，x就会被current.next指向
current.next = x;
current = current.next;//current跟进
}
if(x == end){//如果x是最后一个节点，那么end更新为下一层的最后一个节点
end = x.right;
}
//下一层入队
if(x.left != null){
queue.offer(x.left);
}
if(x.right != null){
queue.offer(x.right);
}
}
return root;
}
}
该方法的额外空间并不符合题目要求，题目要求常数级空间。
-
解法2
思路：递归版本简单明了，遍历到当前节点，如图如遍历到2节点， - 如果
root.left != null也就是说该节点有左右孩子，那么就root.left.next = root.right;，让左孩子指向右孩子。 - 如果
root.next != null该节点的next不为空，让右孩子指向它的next的左孩子root.right.next = root.next.left;。 - 对左右孩子做递归操作。
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;
}
