Easy to read, c++ solution


  • 0
    A

    I tried updating the solution from part I of this problem, but I think it is a bad idea. I just simply started back from scratch and it was easy to come up with a solution.

    The trick here is to find out the next pointers. I created a getNext function that takes care of the next pointers. The solution beats 81% of the other submitted solutions.

    void connect(TreeLinkNode *root) {
        while (root) {
            TreeLinkNode* p = root;
            while (p) {
                if (p->left && p->right) {
                    p->left->next = p->right;
                    p->right->next = getNext(p->next);
                } else if (p->left) {
                    p->left->next = getNext(p->next);
                } else if (p->right) {
                    p->right->next = getNext(p->next);
                }
                p = p->next;
            }
            root = getNext(root);
        }
    }
    
    TreeLinkNode* getNext(TreeLinkNode* node) {
        while (node && !node->left && !node->right) {
            node = node->next;
        }
        return (node ? (node->left ? node->left : node->right) : NULL);
    }

Log in to reply
 

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