My C++ solution, Without Queue, and 0(n) time complexity


  • 0
    U

    '''
    class Solution {
    public:

    TreeLinkNode* NextNode(TreeLinkNode* node)
    {
        if(node == NULL) return NULL;
        else if(node->left != NULL) return node->left;
        else if(node->right != NULL) return node->right;
        else return NextNode(node->next);
    }
    
    void SetupChildren(TreeLinkNode* node)
    {
        if(node == NULL) return;
        else
        {
            if(node->right != NULL)
            {
                node->right->next = NextNode(node->next);
            }
            if(node->left != NULL)
            {
                node->left->next = node->right != NULL ? node->right : NextNode(node->next);
            }
        }
    }
    void connect(TreeLinkNode *root) {
        if(root == NULL) return ;
        else
        {
            /*root->next = NULL;
            queue<TreeLinkNode*> myq;
            myq.push(root);
            while(!myq.empty())
            {
                int size = myq.size();
                for(int i = 0;i < size;i++)
                {
                    TreeLinkNode* tmp = myq.front();
                    myq.pop();
                    if(tmp->left != NULL)
                        myq.push(tmp->left);
                    if(tmp->right != NULL)
                        myq.push(tmp->right);
                    SetupChildren(tmp);
                }
            }*/
            //without queue
            
            TreeLinkNode* first = root;
            while(first != NULL)
            {
                TreeLinkNode* tmp = first;
                first = NextNode(first);
                while(tmp != NULL)
                {
                    SetupChildren(tmp);
                    tmp = tmp->next;
                }
            }
        }
    }
    

    };
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.