原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-medium/xvijdh/

解法一：

/*
// 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) {
        dfs(root,null);
        return root;
    }

    public void dfs(Node currentNode,Node nextNode) {
        if (currentNode == null) {
            return;
        }
        currentNode.next = nextNode;
        dfs(currentNode.left,currentNode.right);
        dfs(currentNode.right,currentNode.next == null ? null : currentNode.next.left);
    }
}

思路：递归的方式解决，递归的出口条件当前指针为null时，递归的操作就是将当前节点的next指向下一个节点，然后将当前节点的左节点作为当前节点，右节点作为下一个节点，然后要考虑一点就是当一层中有多个分支时，就要考虑右节点的下一个节点可能是下一个分支的左节点，然后我们再次递归，但是递归的时候要考虑没有下一个分支了，也就是每一层的最后一个节点。我们只需要判断当前节点的下一个节点是否为null，如果为null就使用null作为下一个节点，如果不为null就使用当前节点的下一个节点的左节点作为下一个节点。