[leetcode] 117 Populate Next Pointer in Binary Tree II

class Solution {
public:
    vector<TreeLinkNode*> lonely;
    int Depth;

    void clean_next(TreeLinkNode * root)
    {
        if(!root) { return; }

        root->next = NULL;

        clean_next(root->left);
        clean_next(root->right);
    }

    int depth(TreeLinkNode * root)
    {
        if(!root) { return 0; }
        return max(depth(root->left), depth(root->right))+1;
    }

    void connect(TreeLinkNode *root) {
        if(!root) { return; }

        Depth = depth(root);
        lonely.resize(Depth+1, NULL);

        clean_next(root);
        connect_impl(root, 0);
    }

    void connect_impl(TreeLinkNode * root, const int depth)
    {
        if(!root) { return; }

        TreeLinkNode * L = root->left;
        TreeLinkNode * R = root->right;

        int d = depth + 1;
        for(; L || R ; ++d)
        {
            TreeLinkNode * n = lonely[d];

            if(L)
            {
                if(n != NULL && n->next == NULL)
                {
                    n->next = L;
                }

                if(R)
                {
                    L->next = R;
                }
                else
                {
                    lonely[d] = L;
                }
                L = L->right ? L->right : L->left;
            }

            if(R)
            {
                if(n != NULL && n->next == NULL)
                {
                    n->next = R;
                }
                lonely[d] = R;

                R = R->left ? R->left : L->right;
            }
        }
        connect_impl(root->left, depth+1);
        connect_impl(root->right, depth+1);
    }
};