117. Populating Next Right Pointers in Each Node II

本题其实想通了，就是一道中等难度的Medium，但是如果想不通，就是Hard。。
换句话说，难度在于思路，而不是实现

本题如果没有空间的要求，就可以用BFS解决，但是因为加了这个要求，就给了人一种无法用BFS解决的错觉，而想办法用DFS解决。应该说或许DFS也能解决，但是BFS解决起来真的不难。

• 尝试连接每一层的所有Node
• 假设上次层的连接好了，就可以运用上一层的Node + 一个for loop连接下一层的所有node
• 需要一个virtualNode帮我们做到这些
• 时间复杂度：
• 空间复杂度:

如上图所示，如果2，3相连，并有一个virtualNode指向4，则很容易将4，5，7相连，代码如下：

/*
// 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) {
    Node head = root;
    while (head != null) {
      Node virtualHead = new Node(-1);
      Node current = virtualHead;
      for (Node tmp = head; tmp != null; tmp = tmp.next) {
        if (tmp.left != null) {
          current.next = tmp.left;
          current = current.next;
        }
        if (tmp.right != null) {
          current.next = tmp.right;
          current = current.next;
        }
      }
      head = virtualHead.next;
    }
    return root;
  }
}