Simple c++ level order traversal with comments


  • 0
    P
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            TreeLinkNode* level = root; // current level
            while(level) {
                TreeLinkNode* runner = level;
                level = NULL;
                // the below loop connects nodes at the next level
                while(runner) {
                    if (runner->left && runner->right) {
                        runner->left->next = runner->right;
                    }
                    
                    TreeLinkNode* left = runner->right ? runner->right : runner->left;
                    TreeLinkNode* temp = runner->next;
                    // find the next node , it should be leftmost child of the current level
                    while(temp && !temp->left && !temp->right) {
                        temp = temp->next;
                    }
                    if (temp && left) {
                        left->next = temp->left?temp->left : temp->right;
                    }
                    // change the level to leftmost non leaf node
                    if ((runner->left || runner->right) && !level) {
                        level = runner->left ? runner->left : runner->right;
                    }
                    runner = temp;
                }
            }
        }
    };

Log in to reply
 

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