What is the difference between these two codes? one accepted one not, please help


  • 0
    R

    Hi, I see that if I define the root outside the loop as you see in the second code, judge does not accept the code, can you tell me what is happing? thanks

    // accepted version    
    typedef TreeNode Node;
        class Solution {
        public:
            vector<TreeNode*> generateTrees(int n) {
                return generateTrees(1,n);
            }
        private:
            vector<Node*> generateTrees(int minV, int maxV) {
                if(minV > maxV)
                    return vector<Node*>{NULL};
                vector<Node*> trees;
                for(int i=minV; i<=maxV; ++i) {
                    vector<Node*> left=  generateTrees(minV, i-1);
                    vector<Node*> right= generateTrees(i+1, maxV);
                    for(int l=0; l<left.size(); ++l){
                       for(int r=0; r<right.size(); ++r){
                            Node* root=new Node(i);            
                            root->left=left[l];
                            root->right=right[r];
                            trees.push_back(root);
                        }
                    }
                }
                return trees;
            }
        };
    

    and now I changed only root definition line:

    // wrong version    
    typedef TreeNode Node;
        class Solution {
        public:
            vector<TreeNode*> generateTrees(int n) {
                return generateTrees(1,n);
            }
        private:
            vector<Node*> generateTrees(int minV, int maxV) {
                if(minV > maxV)
                    return vector<Node*>{NULL};
                vector<Node*> trees;
                for(int i=minV; i<=maxV; ++i) {
                    vector<Node*> left=  generateTrees(minV, i-1);
                    vector<Node*> right= generateTrees(i+1, maxV);
                   Node* root=new Node(i); // I only changed the place of this one
                    for(int l=0; l<left.size(); ++l){
                       for(int r=0; r<right.size(); ++r){            
                            root->left=left[l];
                            root->right=right[r];
                            trees.push_back(root);
                        }
                    }
                }
                return trees;
            }
        };

  • 0
    M

    if root is declare outside, each time you change you assign new value, it modified all reference in tress.


Log in to reply
 

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