题解 | #填充每个节点指向最右节点的next指针 ii#

原始想法(错误)

/**
 * 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;

        if(root->left && root->right)
        {
            root->left->next = root->right;
        }
        if(root->next)
        {
            if((root->left || root->right) && (root->next->left || root->next->right))
            {
                if(root->left && !root->right)
                {
                    TreeLinkNode* node = root;
                    while(node->next && !node->next->left && !node->next->right)
                    {
                        node = node->next;
                    }
                    if(node->next->left) root->left->next = node->next->left;
                    if(node->next->right) root->left->next = node->next->right;
                    /*if(!root->next->left && root->next->right)
                    {
                        root->left->next = root->next->right;
                    }
                    else
                    {
                        root->left->next = root->next->left;
                    }*/
                }
                else
                {
                    TreeLinkNode* node = root;
                    while(node->next && !node->next->left && !node->next->right)
                    {
                        node = node->next;
                    }
                    if(node->next->left) root->right->next = node->next->left;
                    if(node->next->right) root->right->next = node->next->right;
                    /*if(!root->next->left && root->next->right)
                    {
                        root->right->next = root->next->right;
                    }
                    else
                    {
                        root->right->next = root->next->left;
                    }*/
                }
            }
        }
        if(root->next)
        {
            connect(root->next);
        }
        else
        {
            connect(root->left);
            connect(root->right);
        }

    }
};

还是有问题

/**
 * 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;
        queue<TreeLinkNode*> Queue;
        Queue.push(root);
        TreeLinkNode* pre;
        while(Queue.size() >0)
        {
            int size = Queue.size();
            while(size >0)
            {
                TreeLinkNode* node = Queue.front();
                Queue.pop();
                size--;
                if(node->left) Queue.push(node->left);
                if(node->right) Queue.push(node->right);
                if(node->left && node->right)
                {
                    node->left->next = node->right;
                    if(pre->next)
                    {
                        if(pre->left || pre->right)
                        {
                            if(pre->right)
                            {
                                if(node->left || node->right)
                                {
                                    if(node->left) pre->right->next = node->left;
                                    else pre->right->next = node->right;
                                    pre = node;
                                }
                            }
                            else
                            {
                                if(node->left || node->right)
                                {
                                    if(node->left) {pre->left->next = node->left;}
                                    else {pre->left->next = node->right;}
                                    pre = node;
                                }
                            }
                        }
                    }
                    else pre = node;
                }
                else
                {
                    if(pre->next)
                    {
                        if(pre->left || pre->right)
                        {
                            if(pre->right)
                            {
                                if(node->left || node->right)
                                {
                                    if(node->left) pre->right->next = node->left;
                                    else pre->right->next = node->right;
                                    pre = node;
                                }
                            }
                            else
                            {
                                if(node->left || node->right)
                                {
                                    if(node->left) {pre->left->next = node->left;}
                                    else {pre->left->next = node->right;}
                                    pre = node;
                                }
                            }
                        }
                    }
                    else pre = node;
                }
            }
        }
    }
};