C++ Non-recursive BFS with preallocation, no shared nodes, 16ms


  • 0
    A

    All trees returned are independent. No shared nodes between trees at all.
    The DP method is only used to calculate the total number of trees so that we can preallocate the space once for all.

    class Solution {
    public:
        struct Node {
            int val;
            Node *left;
            Node *right;
        };
        uint cn(uint n) {
            vector<uint> dp(n+1, 0);
            dp[0] = dp[1] = 1; dp[2] = 2;
            for (uint k, j, i = 3; i <= n; i++) {
                for (k = i/2, j = 1; j <= k; j++) {
                    dp[i] += dp[j-1] * dp[i-j];
                }
                dp[i] = i%2 ? dp[i]*2+dp[k]*dp[k] : dp[i]*2;
            }
            return dp[n];
        }
        vector<TreeNode*> generateTrees(int n) {
            if (!n) return vector<TreeNode*>({});
            uint m = cn(n);
            vector<TreeNode*> v(m);
            TreeNode *t = (TreeNode*)new Node[m*n];
            for (uint i = 0; i < n; ) {
                t[i].left = NULL;
                t[i].right = NULL;
                t[i].val = ++i;
            }
            v[0] = t;
            for (uint p = n, i = 1; i < n; i++) {
                for (uint e = p, b = 0; b < e; b += n) {
                    TreeNode *k = v[b/n];
                    while (k) {
                        v[p/n] = t+(p+v[b/n]->val-1);
                        memcpy(t+p, t+b, sizeof(TreeNode)*n);
                        for (uint j = 0; j < n; j++) {
                            if (t[b+j].left) t[p+j].left = t[b+j].left+(p-b);
                            if (t[b+j].right) t[p+j].right = t[b+j].right+(p-b);
                        }
                        if (k->right) t[p+i].left = k->right+(p-b);
                        t[p+k->val-1].right = t+(p+i);
                        p += n;
                        k = k->right;
                    }
                    t[b+i].left = t+(b+v[b/n]->val-1);
                    v[b/n] = t+(b+i);
                }
            }
            return v;
        }
    };
    

Log in to reply
 

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