C++ Non-recursive O(1) space solution, based on Morris Traversal


  • 0
    A

    All recursive solutions are NOT constant space solutions, as stack space is also space.

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            TreeLinkNode *p, *q;
            while (root) {
                if (p = root->left) {
                    q = root->right;
                    if (!p->next) p->next = q;
                    while (p->right && p->right != root) {
                        p = p->right;
                        q = q->left;
                        if (!p->next) p->next = q;
                    }
                    if (p->right) {
                        p->right = NULL;
                        root = root->right;
                    } else {
                        p->right = root;
                        root = root->left;
                    }
                } else {
                    root = root->right;
                }
            }
        }
    };
    

Log in to reply
 

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