24ms Easy Iterative and Recursive C++ Solutions


  • 18

    The idea is similar to a level-order traversal and remember to take full advantages of the prefect binary tree assumption in the problem statement.

    The code (iterative solution) is as follows.

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            TreeLinkNode* pre = root;
            TreeLinkNode* cur = NULL;
            while (pre) {
                cur = pre;
                while (cur && cur -> left) { 
                    cur -> left -> next = cur -> right;
                    if (cur -> next)
                        cur -> right -> next = cur -> next -> left;
                    cur = cur -> next;
                }
                pre = pre -> left;
            }
        } 
    };
    

    This problem can also be solved recursively.

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (!root) return;
            if (root -> left) {
                root -> left -> next = root -> right;
                if (root -> next)
                    root -> right -> next = root -> next -> left;
            }
            connect(root -> left);
            connect(root -> right);
        }
    };

  • 1
    H

    Recursive solution does not use constant space, so only iterative solution should be used


  • 2

    Hi, hpplayer. Yeah, you're right. That's just for the completeness of solution sharing :-)


  • 0
    S

    straightforward but O(N) space

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if(!root) return;
            queue<TreeLinkNode*> inqueue,out;
            out.push(root);
            queue<TreeLinkNode*>& outqueue = out;
            
            while(!outqueue.empty())
            {
                TreeLinkNode* tem = outqueue.front();
                outqueue.pop();
                if(!outqueue.empty()) tem->next = outqueue.front();
                if(tem->left) inqueue.push(tem->left);
                if(tem->right) inqueue.push(tem->right);
                if(outqueue.empty())
                {
                    outqueue = inqueue;inqueue = queue<TreeLinkNode*>();
                }    
            }
        }
    };

Log in to reply
 

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