Redundant function call of tree-copy?


  • 0
    U

    a mediocre DP algorithm. in my second for_each loop i called the helper functor to create and insert right-subtrees for a given root with fixed left subtree. however if i don't deep copy the root along with its left child into a new root for every right subtree, a new result will overwrite an old one (since root is passed as a pointer). any idea how i can get rid of the unnecessary tree copy? thanks!

    class AppendRightSubTree    // a helper function object
    {
    public:
       explicit AppendRightSubTree(vector<TreeNode*>& res, TreeNode* root, const int i)
          : m_res(res), m_root(root), m_comp(i)
       {
       }
       void operator()(TreeNode* rootR)
       {
          TreeNode* newRoot = TraverseAdd(m_root, 0);        // deep copy the root and its left subtree
          TreeNode* newR = TraverseAdd(rootR, m_comp);
          newRoot->right = newR;
          m_res.push_back(newRoot);
       }
    private:
       TreeNode* TraverseAdd(TreeNode* root, const int comp)
       {
          if (!root) return NULL;
          TreeNode* newRoot = new TreeNode(root->val + comp);
          newRoot->left = TraverseAdd(root->left, comp);
          newRoot->right = TraverseAdd(root->right, comp);
          return newRoot;
       }
    
       vector<TreeNode*>& m_res;
       TreeNode* m_root;
       const int m_comp;
    };
    
    vector<TreeNode *> generateTrees(int n)
    {
       if (n < 1) return vector<TreeNode*>();
       if (n == 1) return vector<TreeNode*>(1, new TreeNode(1));
       vector<vector<TreeNode*> > cache(1, vector<TreeNode*>(1, nullptr));
       cache.push_back(vector<TreeNode*>(1, new TreeNode(1)));
       for (int i = 2; i <= n; ++i)
       {
          vector<TreeNode*> ith;
          for (int j = 1; j <= i; ++j)
          {
             TreeNode* root = new TreeNode(j);
             std::for_each(cache[j - 1].begin(), cache[j - 1].end(), [=, &ith](TreeNode* subL){
                root->left = subL;     
                // for each root with a fixed left child, append different right subtrees
                std::for_each(cache[i - j].begin(), cache[i - j].end(), AppendRightSubTree(ith, root, j));
             });
          }
          cache.push_back(ith);
       }
       return cache.back();
    }

Log in to reply
 

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