116. Populating Next Right Pointers in Each Node

本题其实并不算难，不过还是没有解出，但是实话实说，中间的思维力度还是有一点大的，想明白就是想明白了，想不明白就是想不明白
最开始我是用Queue做的，虽然做出来了，也不难，但是时间复杂度是，不符合Follow Up里面的时间复杂度的条件[忽略recursive]。。
本题其实用recursive很好解出，但是需要想明白一些事 如上图所示，如果需要Connect 2，3两个黄色的node，及其子树，我们需要：

• link 2->3
  
• recursive Connect 4, 5
  
• recursive Connect 5, 6
  
• recursive Connect 6, 7
  

之后则可以完成

• 时间复杂度：
• 空间复杂度，如果忽略Stack的影响，则是:

代码如下：

/*
// 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) {
    if (root == null) {
      return root;
    }
    if (root.left != null) {
      connectNode(root.left, root.right);
    }
    return root;
  }
  private void connectNode(Node node1, Node node2) {
    node1.next = node2;
    if (node1.left != null) {
      connectNode(node1.left, node1.right);
      connectNode(node1.right, node2.left);
      connectNode(node2.left, node2.right);
    }
  }
}