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

class Solution {
public:
    void connect(TreeLinkNode *root) {
        if (!root) return;
        if (root -> left) {
            root -> left -> next = root -> right;
            if (root -> next)// 比如root在2，2已经在上一层作为左子指向右子3了，所以root->next不为NULL,这样handle了子树间大儿子最右要和二儿子最左相连接
                root -> right -> next = root -> next -> left;
        }
        connect(root -> left);
        connect(root -> right);
    }
};

class Solution {
public:
    void connect(TreeLinkNode *root) {
        TreeLinkNode* pre = root;
        TreeLinkNode* cur = NULL;
        while (pre) {
            cur = pre;
            while (cur && cur -> left) { 
                cur -> left -> next = cur -> right;
                if (cur -> next)
                    cur -> right -> next = cur -> next -> left;
                cur = cur -> next;
            }
            pre = pre -> left;
        }
    } 
};

/*
        4. Another constant iterator version.
    */
    public void connect(TreeLinkNode root) {
        if (root == null) {
            return;
        }

        TreeLinkNode leftEnd = root;
        while (leftEnd != null && leftEnd.left != null) {
            TreeLinkNode cur = leftEnd;
            while (cur != null) {
                cur.left.next = cur.right;
                cur.right.next = cur.next == null ? null: cur.next.left;

                cur = cur.next;
            }

            leftEnd = leftEnd.left;
        }
    }

REF:

results matching ""

    No results matching ""