leetcode 116.填充每个节点的下一个右侧节点指针

题目

思路

还是层序遍历。根据题意，当遍历到该层最后一个节点时，将其next置为null。else的话，则指向它的下一个节点。

怎么做呢？当我们把当前节点出队的时候，此时队头的元素就是我们的下一个节点。所以只需要cur.next= queue.peek()即可。

此外，我觉得这道题的输出示例给的不对，输出给的是一个list，但是代码要返回的是一个node类型。我最后看了看参考代码，返回根节点即可。

代码

//leetcode submit region begin(Prohibit modification and deletion)
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    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 root;
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);  //入队
        while (!queue.isEmpty()) {
            int len = queue.size();
            Node pre = new Node();
            while (len > 0) {
                Node temp = queue.poll(); //出队
                //将每层最后一个节点的next为Null
                if (len == 1) {
                    temp.next = null;
                }else{
                    temp.next=queue.peek(); //当前节点出队后，此时queue的peek就是下一个节点
                }
                if (temp.left != null) //有左入左
                    queue.add(temp.left);
                if (temp.right != null) //有右入右
                    queue.add(temp.right);
                len--;
            }
        }
        return root;
    }
}
//leetcode submit region end(Prohibit modification and deletion)