/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* p = root -> next;
        while(p){
            if(p -> left){
                p = p -> left;
                break;
            }
            if(p -> right){
                p = p -> right;
                break;
            }
            p = p -> next;
        }
        if (root->right) root->right->next = p;
        if (root->left) root->left->next = root->right ? root ->right : p;
        connect(root->right);
        connect(root->left);
    }
};

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  TreeLinkNode *left, *right, *next;
 *  TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
 * };
 */
class Solution {
public:
//此解法先设定一个每一层的最左值。因为树有缺失，最左值可能是上一层的左孩子，也有可能是右孩子。所以依然要记录上一层。因为上一层的右孩子可能会缺失，所以上一层要往右移，直到移到有孩子的节点，然后才能把next指针连上。这种方法space是O(1)
    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode* leftMost = root;
        while(leftMost){
            TreeLinkNode* p = leftMost;
            while(p && !p -> left && !p ->right){
                p = p -> next;//p要移到第一个有孩子的节点
            }
            if(!p) return;
            leftMost = p -> left ? p -> left : p -> right;//leftMost下移一层
            TreeLinkNode* cur = leftMost;
            while(p){
                if(cur == p -> left){//判断current node是上一层的左孩子还是右孩子{
                    if(p -> right){
                        cur -> next = p -> right;//如果右孩子没有缺失，则连上next
                        cur = cur -> next;//cur节点也要往右走
                    }
                    p = p -> next;
                }else if(cur == p -> right){
                    p = p -> next;
                }else{
                    //while(p && !p -> left && !p -> right){
                    if(!p->left && !p->right){//上一层要往右移，直到移到有孩子的节点，然后才能把next指针连上
                        p = p -> next;
                        continue;
                    }
                    cur -> next = p -> left ? p -> left : p -> right;
                    cur = cur -> next;
                }
            }
        }
    }
};