每个节点的右向指针

给定一个二叉树

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);
    }
}