给定一个二叉树
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
}
填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。
说明:
你只能使用额外常数空间。
使用递归解题也符合要求，本题中递归程序占用的栈空间不算做额外的空间复杂度。
你可以假设它是一个完美二叉树（即所有叶子节点都在同一层，每个父节点都有两个子节点）。
思路
在层序遍历的基础上进行修改，遍历某一层，需注意是否遍历到该层最后一个节点
public class Solution {
public void connect(TreeLinkNode root) {
if(root!=null){
Queue<TreeLinkNode> q=new LinkedList<TreeLinkNode>();
q.offer(root);
while(!q.isEmpty()){
int size=q.size();
int c=0;
for(int i=0;i<size;++i){
TreeLinkNode temp=q.poll();
if(c==size-1){
temp.next=null;
}else{
temp.next=q.peek();
}
if(temp.left!=null){
q.offer(temp.left);
}
if(temp.right!=null){
q.offer(temp.right);
}
c++;
}
}
}
}
}
思路
对于next为null，可以不做任何处理，该值会自动初始化为null
public class Solution {
public void connect(TreeLinkNode root) {
if(root==null){
return ;
}
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);
}
}
