C++ solution, O(1) in space with comment on how to build the bridge


  • 0
    T
    1. First of all, we build the wall for each layer by pointing the rightmost to NULL.
    2. Secondly, for each of the node, firstly we build the bridge between the left child node and the right child node; secondly we build the bridge between the right child of the node and the left child of the next node in that layer, iteration until hit the wall - NULL.
    3. Next to the left to catch again the head of the new layer.
    class Solution {
    public:
        void connect(TreeLinkNode *root) {
            if (!root) return;
            //build NULL
            TreeLinkNode *current = root;
            while (current->right){
                current->next = NULL;
                current = current->right;
            }
            //set of beginning of each layer ->setCurr
            TreeLinkNode *setCurr = root;
            current = root;
            while (setCurr->left){
                //for each node, build a bridge from left to right
                current->left->next = current->right;
                //build bridge between right child of node 1 and left child of node 2
                if (current->next){
                    current->right->next = current->next->left;
                    current = current->next;
                }
                else{
                    current = setCurr = setCurr->left;
                }
            }
            return;
        }
    };
    

  • 0
    T

    Well actually dont need the first step since the rightmost already point to NULL.


Log in to reply
 

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