C++ solution with 32ms execution time, O(n) time and O(1) space complexity, and only 25 lines


  • 0
    R

    Hi all, introducing my solution to this problem in C++:

    Essentially it takes a BFS approach with implementation in queue. The key idea here is that it's going to pop up from the queue a few elements each time. The number of elements being popped is determined by the width of the tree at the level at which the program is currently looking at.

    If you look at the example given in the question description page. The first time it's going to pop up 1 element from the queue, the second time 2 elements, and the third time 3 elements.

    Each time all the elements popped from the queue would be connected with the 'next' field in each node, and the last node's 'next' would be set to NULL.

    Please take a look at the code below:)

    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (root == NULL) return;
            queue<TreeLinkNode*> my_q;
            my_q.push(root);
            int width = 1; // the width at the first level
            while(!my_q.empty()) {
                TreeLinkNode* first = my_q.front(); // the first node at each level
                // next_width is the width at the next level.
                int next_width = 0;
                for (int i = 0; i < width; i++) {
                    if (my_q.front()->left != NULL) {
                        my_q.push(my_q.front()->left);
                        next_width++;
                    }
                    if (my_q.front()->right != NULL) {
                        my_q.push(my_q.front()->right);
                        next_width++;
                    }
                    first->next = my_q.front(); // make the connection
                    first = first->next; // iterate through the current level
                    my_q.pop();
                }
                width = next_width; // ready to go into the next level, so update 'width' with 'new_width'
                first->next = NULL; // this is the end of the current level, set the 'next' field of the last node to be NULL
            }
        }
    };
    

Log in to reply
 

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