填充每个节点的下一个右侧节点指针I/II

题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/ 参考：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/solution/tian-chong-mei-ge-jie-dian-de-xia-yi-ge-you-ce-j-3/

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        /*
        *巧用next层次遍历，空间复杂度O(1)
        */
        if(root == nullptr) return root;
        Node * left_most = root;
        while(left_most->left != nullptr) {//从上到下遍历
            Node *head = left_most;
            while(head != nullptr) {//从左到右遍历
                head->left->next = head->right;
                if(head->next != nullptr)
                    head->right->next = head->next->left;
                head = head->next;
            }
            left_most = left_most->left;
        }
        return root;
    }
};

进阶：给的二叉树非满二叉树 题目：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node-ii/

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

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/
class Solution {
public:
    Node* connect(Node* root) {
        /*
        *巧用next层次遍历，空间复杂度O(1)
        */
        if(root == nullptr) return root;
        Node * left_most = root;
        while(left_most != nullptr) {//从上到下遍历
            Node *head = left_most;
            while(head != nullptr && head->left == nullptr && head->right == nullptr) {
                    head = head->next;
            }
            left_most = head;//更新下一层的left_most
            while(head != nullptr) {//从左到右遍历
                Node *nxt = head->next;//head的下一个 子节点非空 节点
                while(nxt != nullptr && nxt->left == nullptr && nxt->right == nullptr)
                    nxt = nxt->next;
                if(head->left != nullptr) {
                    if(head->right != nullptr) {
                        head->left->next = head->right;
                        if(nxt != nullptr)
                            head->right->next = nxt->left ? nxt->left:nxt->right;
                    }
                    else if(nxt != nullptr)
                        head->left->next = nxt->left ? nxt->left:nxt->right;
                }else {
                    if(nxt != nullptr)
                        head->right->next = nxt->left ? nxt->left:nxt->right;
                }
                head = nxt;
            }
            if(left_most == nullptr) break;
            left_most = left_most->left ? left_most->left:left_most->right;
        }
        return root;
    }
};