O(1) space O(N) time C++ Solution


  • 0
    F
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (!root) return;
            TreeLinkNode* head = nullptr; // record the start of the next level
            TreeLinkNode* prev = nullptr; // link by the prev pointers
            TreeLinkNode* cur = root; //current node of the current level
            while (cur != nullptr) {
                while (cur != nullptr) {
                    if (cur->left) {
                        if (prev) {
                            prev->next = cur->left;
                        }
                        else {
                            head = cur->left;
                        }
                        prev = cur->left;
                    }
                    if (cur->right) {
                        if (prev) {
                            prev->next = cur->right;
                        }
                        else {
                            head = cur->right;
                        }
                        prev = cur->right;
                    }
                    cur = cur->next;
                }
                cur = head;
                head = nullptr;
                prev = nullptr;
            }
        }
    };

Log in to reply
 

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