C++ iterative solution


  • 0
    B

    The intuitive solution is using a queue to traverse the tree level by level, like this solution. Now we have each layer connected with next pointer, then each level becomes a linked list. So we only need to keep the head node of each level.

    class Solution {
    public:
        void connect(TreeLinkNode *root) 
        {
            TreeLinkNode * head = root;
            while(head)
            {
                TreeLinkNode * probe = head;
                while(probe)
                {
                    if(!probe -> left && !probe -> right)
                    {
                        probe = probe -> next;
                        continue;
                    }
                    TreeLinkNode * temp = probe -> next;
                    while(temp && !temp -> left && !temp -> right) temp=temp->next;
                    TreeLinkNode * temp1 = temp;
                    if(temp) temp1 = temp->left ? temp -> left : temp -> right;
                    if(probe -> right) probe -> right -> next = temp1;
                    if(probe -> left ) probe -> left -> next = probe -> right ? probe -> right : temp1;
                    probe = temp;
                }
                
                while(head)
                {
                    TreeLinkNode * temp = head -> left ? head -> left : head -> right;
                    if(temp)
                    {
                        head = temp;
                        break;
                    }
                    head = head -> next;
                }
    
            }
        }
    };

Log in to reply
 

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