117. 填充每个节点的下一个右侧节点指针 II

解法一：广度优先遍历

层序遍历，给当前层每一个结点安排上 next 。不过这样做没有满足常数级额外空间的要求。

/*
// 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) {
        Queue<Node> nodes = new LinkedList<>();
        if (root != null) {
            nodes.offer(root);
        }
        while (!nodes.isEmpty()) {
            int size = nodes.size();
            Node last = nodes.poll();
            if (last.left != null) {
                nodes.offer(last.left);
            }
            if (last.right != null) {
                nodes.offer(last.right);
            }
            for (int i = 0; i < size - 1; ++i) {
                Node cur = nodes.poll();
                if (cur.left != null) {
                    nodes.offer(cur.left);
                }
                if (cur.right != null) {
                    nodes.offer(cur.right);
                }
                last.next = cur;
                last = cur;
            }
            last.next = null;
        }
        return root;
    }
}

解法二

参考官方题解：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-15/

/*
// 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 {
    // 上一个结点
    private Node lastNode;
    // 下一层第一个结点
    private Node firstNode;
    public Node connect(Node root) {
        Node begin = root;
        while (begin != null) {
            lastNode = null;
            firstNode = null;
            for (Node i = begin; i != null; i = i.next) {
                if (i.left != null) {
                    handle(i.left);
                }
                if (i.right != null) {
                    handle(i.right);
                }
            }
            begin = firstNode;
        }
        return root;
    }
    private void handle(Node p) {
        // 不是下一层第一个结点
        if (lastNode != null) {
            lastNode.next = p;
        }
        // 记录下一层第一个结点
        if (firstNode == null) {
            firstNode = p;
        }
        lastNode = p;
    }
}