Tree - 116. Populating Next Right Pointers in Each Node

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

**Input:** {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}

**Output:** {"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}

**Explanation:** Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B.

``` 

**Note:**

*   You may only use constant extra space.
*   Recursive approach is fine, implicit stack space does not count as extra space for this problem.

**思路：**
> 给一棵满二叉树，让把next指针指向同一层，很简单，可以先序遍历做，也可以只用两个指针，核心代码就是对于一个节点，左节点指向右节点，右节点指向自己的下一个的左节点。因为题目要求`only use constant extra space`,所以不能用递归，递归其实也是用了额外的空间。

**代码：**

java：
/*
// Definition for a Node.
 class Node {
 public int val;
 public Node left;
 public Node right;
 public Node next;

public Node() {}

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) {
 recursion(root);
 return root;
 }

private void recursion(Node root) {
    if (root == null) return;
    
    if (root.left != null) root.left.next = root.right;
    if (root.right != null && root.next != null) root.right.next = root.next.left;
    
    recursion(root.left);
    recursion(root.right);
}*/

public Node connect(Node root) {
    Node level_start = root;
    
    while (level_start != null) {
        Node cur = level_start;
        while (cur != null) {
            if(cur.left != null) cur.left.next = cur.right;
            if(cur.right != null && cur.next != null) cur.right.next = cur.next.left;
            
            cur = cur.next;
        }
        level_start = level_start.left;
    }
    
    return root;
 }
}