7-line O(1) space recursive solution + O(logN) space solution (detailed explanation and picture illustration)


  • 0

    This is the recursive solution inspired by @G513.
    Key observation: A node x's next node is:

    • x's right sibling if it has one;
    • otherwise, x's next non-leaf uncle's left-most child if it has one;
    • otherwise, NULL.
      0_1481668086897_nextnode2.JPG

    The algorithm will first populate next pointers of root->right and root->left, then do recursion on root->right before root->left (because we need next uncle's next pointers populated before current node). Since no local variables are defined, so it should be O(1) space on recursion stack (?).

        void connect(TreeLinkNode *r) {
            if (!r) return;
            if (r->right) r->right->next = find_next(r->next);
            if (r->left)  r->left->next = r->right? r->right : find_next(r->next);
            connect(r->right); connect(r->left); // must do recursion on right subtree first
        }
        // find next non-leaf same level node's left-most child
        TreeLinkNode* find_next(TreeLinkNode *r) {
            while (r && !r->left && !r->right) r = r->next; // find next non-leaf node
            return r? r->left ? r->left : r->right : NULL;  // return left-most child
        }
    

    If O(logN) space is allowed instead of O(1), we could save the current next node of each level instead of looking for next non-leaf uncle's:

        vector<TreeLinkNode*> rightNodes;  // index is tree level  
        void connect(TreeLinkNode *r) { connectAtLevel(r); }    
        void connectAtLevel(TreeLinkNode *r, int level = 0) {
            if (!r) return;
            if (rightNodes.size() == level) { r->next = NULL; rightNodes.push_back(r); }
            else { r->next = rightNodes[level];  rightNodes[level] = r; }
            connectAtLevel(r->right, level+1); connectAtLevel(r->left, level+1);
        }
    

  • 0

    @zzg_zzm Great Idea! but I doubt it it's real O(1) extra Space, I found some discussions on Google, and this may be useful for analyzing: a recursive algorithm will require space O(depth of recursion), the tree depth maybe reach to Lg(n) on average case, and connect() may need to reach to !r which indicates it reaches to some leaf already.


Log in to reply
 

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