LC116.填充每个节点的下一个右侧节点指针（迭代法）

LC116.填充每个节点的下一个右侧节点指针（迭代法） 题目

查看题目

解题思路

模板题，层序遍历，因为题目给出是完全二叉树，所以不需要考虑在中间位置节点的next指针指向null。注意点：

• 每一层的最后一个节点的next指向null即可。
• 中间节点的next指向自己的右节点，注意连接时用peekpeekFirst()而不要pollFirst()。

代码

// 使用层序遍历进行解答的时候，也是要留心最后一个节点，将最后一个节点的next指向null

class Solution {
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }     
        Deque que = new linkedList<>();

        que.offerLast(root);
        while (!que.isEmpty()) {
            int levelsize = que.size();
            for (int i  = 0; i < levelsize; i++) {
                Node node = que.pollFirst();
                if (node.left != null) {
                    que.offerLast(node.left);
                }
                if (node.right != null) {
                    que.offerLast(node.right);
                }
                if (i == levelsize - 1) {
                    node.next = null;
                } else {
                    // 这里要使用peekFirst而不是pollFirst，不要推出队列，读一下就可以
                    node.next = que.peekFirst();
                }
            }
        } 
        return root;
    }
    
}