Single While Loop C++ solution


  • 0
    S

    Just use single one while loop and if statements to deal with different situations.
    wondering if it can be made faster. Currently it takes 120ms

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            TreeLinkNode* pCurr = root;
            TreeLinkNode* pLastOneSeen = NULL;
            TreeLinkNode* pNextLevelHead = NULL;
            while (pCurr) {
                if ((pCurr->left) && (pCurr->right)){
                    // contain both
                    if (pLastOneSeen){
                        pLastOneSeen->next = pCurr->left;
                    }
                    pLastOneSeen = pCurr->left->next = pCurr->right;
                    if (pNextLevelHead == NULL){
                        pNextLevelHead = pCurr->left;
                    }
                }
                else if (pCurr->left){
                    // only left
                    if (pLastOneSeen){
                        pLastOneSeen->next = pCurr->left;
                    }
                    pLastOneSeen = pCurr->left;
                    if (pNextLevelHead == NULL){
                        pNextLevelHead = pCurr->left;
                    }
                }
                else if (pCurr->right){
                    // only right
                    if (pLastOneSeen){
                        pLastOneSeen->next = pCurr->right;
                    }
                    pLastOneSeen = pCurr->right;
                    if (pNextLevelHead == NULL){
                        pNextLevelHead = pCurr->right;
                    }
                }
                else{
                    // no children, do nothing
                }
    
                
                if (pCurr->next == NULL){
                    // last node of current level
                    // go to next level
                    pCurr = pNextLevelHead;
                    pNextLevelHead = NULL;
                    pLastOneSeen = NULL;
                }
                else{
                    pCurr = pCurr->next;
                }
            }
        }
    };

Log in to reply
 

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