O(depth) space recursive C++ solution (not O(1) space but still clean and straightforward)


  • 0

    Only after I finished the solution I realized that the problem requires only O(1) space. The following solution uses O(depth) space to store the current right node of each level and uses "reversed pre-order" traversal (i.e., parent->right child->left child) for recursion.

    class Solution {
    public:
        vector<TreeLinkNode*> rightNodes; // rightNodes[i]: the current right node at level i
        void connect(TreeLinkNode *r) {
            connectAtLevel(r);
        }
            
        void connectAtLevel(TreeLinkNode *r, int level = 0) {
            if (!r) return;
            if (rightNodes.size() == level) { // node "r" is the rightmost node of this level
                r->next = NULL;
                rightNodes.push_back(r);
            }
            else { // use previously stored right node as the ->next of the current node at this level
                r->next = rightNodes[level];
                rightNodes[level] = r;
            }
            connectAtLevel(r->right, level+1);
            connectAtLevel(r->left, level+1);
        }
    };
    

Log in to reply
 

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