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

解法一：next指针

同117. 填充每个节点的下一个右侧节点指针 II。利用 next 指针在本层中遍历，并填充下一层的 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 {
    // 本层上一个结点
    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 (firstNode == null) {
            firstNode = p;
        }
        if (lastNode != null) {
            lastNode.next = p;
        }
        lastNode = p;
    }
}