Solution which generate a batch independent trees but not a flow graph


  • 0
    Z

    This solution beats 91.82% solution when submitted.

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<TreeNode*> generateTrees(int n) {
            //vector<TreeNode*> res;
            vector<vector<TreeNode*>> res(n+1,vector<TreeNode*>{});
            if(!n) return res[n];
            res[0].push_back(NULL);
            generateTrees(res,n);
            return res[n];
            
        }
        
        void generateTrees(vector<vector<TreeNode*>>& res,int n){
            if(n>1) generateTrees(res,n-1);
            for(int i=1;i<=n;i++){
            for(auto le:res[i-1])
            for(auto ri:res[n-i]){
                TreeNode* root = new TreeNode(i);
                root->left = copy(le,0);
                root->right = copy(ri,i);
              
                res[n].push_back(root);
            }
            }
            
            
            
        }
        
        TreeNode* copy(TreeNode* root, int offset){
            if(!root) return NULL;
            TreeNode* newroot = new TreeNode(root->val+offset);
            newroot->left = copy(root->left,offset);
            newroot->right = copy(root->right,offset);
            return newroot;
        }
    };
    

    The problem looks easy and I have go through lots of solutions but I think most of them only return a list of trees sharing subtrees nodes, so they are not independent trees but more like a "flow graph".

    What's the risk of this? It means user should not modify any tree node otherwise access to another tree in the list will lead to a wrong value. Since the problem statement doesn't imply the trees will be read-only, the correct result should be a list of independent trees.

    Please correct me if my understanding is wrong. Any discussion is welcome!


Log in to reply
 

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