What is wrong with my code?


  • 0
    X

    my idea is first to generate sequences, such as "123","132","213","321","312" and use each sequence to construct a BST.

    the head of the sequence is the root of the tree, and the rest numbers greater than the head are its right children, when we insert a new number, such as 4, we only need to insert it before its right children, or as a new head. you can imagine how to add a greater number in the real BST.enter code here

    the first sequence is "1",
    and for each number i from 2 to n, we insert this i into each sequence to generate a new sequence, the insert position is before a number that greater or equal to the head of this sequence.
    such as insert 2 to "1", because the the first number 1 >=1, so the new sequence is "21", we create this new sequence and append to the end, we also modify the original sequence by append the i at the end, as "12", so the result is "12","21"

    we continue insert the 3 to "12","21", to insert 3 to "12", because 1>=1, so "312",because 2 >1, so "132", and then append the 3 at the end so "123", so we get "312","132","123"
    to insert 3 to "21", we get "321", because 1<2, so we don't insert 3 between 2 and 1. then we append the 3 at the end to get "213". the final result is "312","132","123","321","213".

    I test my program can get the correct result, but I don't know why it cannot pass the test.

    void InsertTreeNode(TreeNode* root, int num)
    {
        
        if (root->val > num)
        {
            if (root->left == NULL)
            {
                root->left = new TreeNode(num);
            }
            else {
                InsertTreeNode(root->left, num);
            }
        }
        else {
            if (root->right == NULL)
            {
                root->right = new TreeNode(num);
            }
            else {
                InsertTreeNode(root->right, num);
            }
        }
    }
    
    
    
    vector<TreeNode *> generateTrees(int n) {
        vector<TreeNode *> trees;
        if (n < 1)
        {
            return trees;
        }
        vector<vector<int>*> seqnumbers;
        int seqSize = 1;
        seqnumbers.push_back(new vector<int>);
        seqnumbers[0]->push_back(1);
        for (int i = 2; i <= n; i++)
        {
            unsigned int size = seqnumbers.size();
            for (unsigned int j = 0; j < size; j++)
            {
                vector<int> *pSeq = seqnumbers[j];
                int rightChildnum = 0;
                for (unsigned int k = 0; k < pSeq->size(); k++)
                {
                    if (pSeq->at(k) > rightChildnum)
                    {
                        vector<int> *pNew = new vector<int>(*pSeq);
                        pNew->insert(pNew->begin() + k, i);
                        seqnumbers.push_back(pNew);
                        rightChildnum = pSeq->at(k);
                    }
                }
                pSeq->push_back(i);
            }
        }
    
        for (unsigned int i = 0; i < seqnumbers.size(); i++)
        {
    
            vector<int> * pSeq = seqnumbers[i];
            printNumbers(*pSeq);
            TreeNode *root = new TreeNode(pSeq->at(0));
            for (unsigned int j = 1; j < pSeq->size(); j++)
            {
                InsertTreeNode(root, pSeq->at(j));
            }
            trees.push_back(root);
        }
    
        for (unsigned int i = 0; i < seqnumbers.size(); i++)
        {
            delete seqnumbers[i];
        }
    
        return trees;
    }

Log in to reply
 

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