# [117. Populating Next Right Pointers in Each Node II](https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/)

# 思路
题目要求将二叉树同一层的节点用指针串起来，要求空间复杂度O(1)。
这题是[116](https://leetcode.com/problems/populating-next-right-pointers-in-each-node/)的升级版，116中的二叉树是满二叉树，比较简单，但思路其实也是类似的，可先参考[116题解](https://github.com/ShusenTang/LeetCode/blob/master/solutions/116.%20Populating%20Next%20Right%20Pointers%20in%20Each%20Node.md)。
## 思路一
最好想的还是递归: 如果root的左右子树都已经串好了的话，那么我们只需要将左子树每一层的最右边的节点(代码中用last_left表示)的next指向右子树对应层最左边节点(代码中用start_right表示)即可。          
我们分别用start_left和start_right代表左右子树某层的最开始节点。然后我们可以从start_left一路向右(即一路next)找到左子树此层最右边那个节点last_left, 然后我们将其next指向start_right，然后更新指针start_left和start_right进入下一层。

## 思路二
也可以用非递归的方式。我们先new一个节点head作为每一层的头结点，然后从开始从左往右从上往下遍历，然后用cur记录当前节点（初始化为head），遇到下一个节点就将cur的next指向cur，然后更新cur。

# C++
## 思路一
``` C++
class Solution {
public:
    Node* connect(Node* root) {
        if(root == NULL) return NULL; // 递归出口
        Node *start_left = connect(root -> left);
        Node *start_right = connect(root -> right);
        
        while(start_left && start_right){
            Node *last_left = start_left;
            while(last_left -> next) last_left = last_left -> next;
            last_left -> next = start_right;
            
            // 更新start_left
            while(!start_left->left && // 无左子树
                  !start_left->right && // 无右子树
                  start_left -> next != start_right) // 不是此层最后一个节点
                start_left = start_left -> next;
            if(start_left -> left) start_left = start_left -> left;
            else start_left = start_left -> right;

            // 更新start_right
            while(!start_right->left && // 无左子树
                  !start_right->right && // 无右子树
                  start_right -> next) // 不是此层最后一个节点
                start_right = start_right -> next;
            if(start_right -> left) start_right = start_right -> left;
            else start_right = start_right -> right;
            
        }
        return root;
    }
};
```

## 思路二
``` C++
class Solution {
public:
    Node* connect(Node* root) {
        Node *head = new Node(0, NULL, NULL, NULL);
        Node *p = root, *cur = head;
        while(p){
            if(p -> left){
                cur -> next = p -> left;
                cur = cur -> next;
            }
            if(p -> right){
                cur -> next = p -> right;
                cur = cur -> next;
            }
            
            p = p -> next;
            if(!p){ // 到达一层的结尾
                p = head -> next;
                head -> next = NULL; // 清空头结点
                cur = head;
            }      
        }
        return root;
    }
};
```