Share my several solutions using C++,easy to understand


  • 0
    V

    (1)Recursion

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL || root->left == NULL) //We may assume that it is a perfect binary tree,so (root->left == NULL) equal (root->left == NULL && root->right == NULL)
                return;
            
            root->left->next = root->right;
            
            if (root->next != NULL)
                root->right->next = root->next->left;
            
            connect(root->left);
            connect(root->right);
        }
    };
    

    (2)Iteration, the space complexity is O(1)

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL || root->left == NULL) 
                return;
            
            TreeLinkNode *temp = root;
            
            while(temp->left != NULL)
            {
                while (temp != NULL)//every time we just handle nodes in the same level,starting form the first node in current level
                {
                    temp->left->next = temp->right;
                    if (temp->next != NULL)
                        temp->right->next = temp->next->left;
                    
                    temp = temp->next;
                }
                
                root = root->left;
                temp = root;
            }
        }
    };
    

    (3)Using queue,it's very easy to understand although it doesn't meet the requirement.You can refer to the solution

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL) return;
            
            queue<TreeLinkNode *>q;
            int current_level = 0;//means total nodes in the current level
            TreeLinkNode *node = NULL, *nodeRight = NULL;
            q.push(root);
            
            while (!q.empty())
            {
                current_level = q.size();
                node = q.front();
                q.pop();
                --current_level;
                
                while (true)
                {
                    if (node->left != NULL)
                        q.push(node->left);
                    if (node->right != NULL)
                        q.push(node->right);
                        
                    if (current_level == 0)
                    {
                        node->next = NULL;
                        break;
                    }
                    else
                    {
                        nodeRight = q.front();
                        q.pop();
                        --current_level;
                        node->next = nodeRight;
                        node = nodeRight;
                    }
                }
            }
        }
    };

Log in to reply
 

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