Recursive c++ 15 lines


  • 3
    F
    class Solution {
    public:
       std::vector<TreeNode*> generateTrees(int n2, int n1=1) {
          std::vector<TreeNode*> TreeHeads;
          for(int i=n1; i<=n2; ++i) {
             auto LeftTrees = i==n1 ? std::vector<TreeNode*>{nullptr} : generateTrees(i-1, n1);
             auto RightTrees = i==n2 ? std::vector<TreeNode*>{nullptr} : generateTrees(n2, i+1);
             for( auto pleft : LeftTrees )
                for( auto pright : RightTrees ) {
                   auto head = new TreeNode(i);
                   head->left = pleft; head->right = pright;
                   TreeHeads.push_back(head);
                }
          }
          return TreeHeads;
       }
    };
    
    

  • 0

    I have the same idea to construct the n-node tree using previous smaller trees as left and right subtrees. However, I used DP and a helper function to make deep copy with node value shifted, I feel it has be to redundant and uses too much space to store all trees of less than n nodes even though we only need n-node trees. Thanks for sharing the solution.

    I attached my code below.

        vector<TreeNode*> generateTrees(int n) {
            if (n <= 0) return {};
            // DP to store the results from 1 node and n nodes (which uses too much space)
            vector<vector<TreeNode*>> res(n+1);
            res[0] = { NULL };
            for (int i = 1; i <= n; i++) {
                for (int k = 1; k <= i; k++) {
                    for (auto& L:res[k-1]) {
                        for (auto& R:res[i-k]) {
                            TreeNode* r = new TreeNode(k);
                            r->left = deppCopyShift(L, 0); 
                            r->right = deppCopyShift(R, k);
                            res[i].push_back(r);
                        }
                    }
                    
                }
            }
            return res[n];
        }
        
        TreeNode* deppCopyShift(TreeNode* r, int x) {
            TreeNode* copy_r = NULL;
            if (!r) return copy_r;
            
            copy_r = new TreeNode(r->val+x);
            copy_r->left = deppCopyShift(r->left, x);
            copy_r->right = deppCopyShift(r->right, x);
            return copy_r;
        }
    
    

Log in to reply
 

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