PU Populating Next Right Pointers in Each Node II

         1
       /  
      2    3
     /     
    4   5    7

         1 -> NULL
       /  
      2 -> 3 -> NULL
     /     
    4-> 5 -> 7 -> NULL

# Definition for binary tree with next pointer.
# class TreeLinkNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#         self.next = None

class Solution:
    # @param root, a tree link node
    # @return nothing
    def connect(self, root):
        while True:
            #find the firstone _root, record
            while root and not root.left and not root.right:
                root = root.next
            if not root: return
            nextlevel = root.left if root.left else root.right
            while True:
                if root.left and root.right:
                    root.left.next = root.right
                _root = root.next
                while _root and not _root.left and not _root.right:
                    _root = _root.next
                if not _root: break
                left = root.right if root.right else root.left
                right = _root.left if _root.left else _root.right
                left.next = right
                root = _root
            root = nextlevel

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
void connect(struct TreeLinkNode *root) {
    while (1) {
        while (root && !root->left && !root->right) root = root->next;
        if (!root) return;
        struct TreeLinkNode *next = root->left ? root->left : root->right;
        while (1) {
            if (root->left && root->right) root->left->next = root->right;
            struct TreeLinkNode *_root = root->next;
            while (_root && !_root->left && !_root->right) _root = _root->next;
            if (!_root) break;
            struct TreeLinkNode *l = root->right ? root->right : root->left;
            struct TreeLinkNode *r = _root->left ? _root->left : _root->right;
            l->next = r;
            root = _root;
        }
        root = next;
    }
}

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
void connect(struct TreeLinkNode *root) {
    struct TreeLinkNode *head = 0, *pre = 0, *cur = root;
    while (cur) {
        while (cur) {
            if (cur->left) {
                if (pre) pre->next = cur->left;
                else head = cur->left;
                pre = cur->left;
            }
            if (cur->right) {
                if (pre) pre->next = cur->right;
                else head = cur->right;
                pre = cur->right;
            }
            cur = cur->next;
        }
        cur = head;
        head = pre = 0;
    }
}

/**
 * Definition for binary tree with next pointer.
 * struct TreeLinkNode {
 *  int val;
 *  struct TreeLinkNode *left, *right, *next;
 * };
 *
 */
void connect(struct TreeLinkNode *root) {
    struct TreeLinkNode dummy, *p = &dummy;
    p->next = 0;
    while (root) {
        if (root->left) p = p->next = root->left;
        if (root->right) p = p->next = root->right;
        if (root->next) root = root->next;
        else {
            root = dummy.next;
            dummy.next = 0;
            p = &dummy;
        }

    }
}