Neat C++ solution, constant space, with explanations

  • 0

    We are likely to think about level order traversal using a queue at the first glance at this problem. However, using a queue doesn't meet the demand of constant space. And it's tricky to connect two nodes with different parents. But wait, when we connect all nodes in a level, we can take that level as a queue, and we can do exactly what we did level order traversal. Then we have the following code:

    void connect(TreeLinkNode *root) {
        if (!root) return;
        TreeLinkNode *cur = root, *leftest = root;
        while (leftest->left) {
     	    cur->left->next = cur->right;
     	    if (cur->next) {
     		    cur->right->next = cur->next->left;
     		    cur = cur->next;
     	    } else {
     		    cur = leftest->left;
     		    leftest = cur;

    Note that we need a pointer leftest pointing to the first node in current level so that we can go to the first node in next level by visiting its left child. And if the new leftest doesn't have a left child, we are done, since it's a perfect binary tree.

Log in to reply

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