# Redundant function call of tree-copy?

• 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
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);
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();
}``````

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