My solution based on LeetCode 096 using DP.


  • 0
    S

    Based on LeetCode 096: Unique Binary Search Trees.

    It runs faster without deleteTree.

    class Solution0 : public Solution {
      public:
        std::vector<TreeNode*> generateTrees(int n) {
          if (!n) return std::vector<TreeNode*>();
          std::vector<std::vector<TreeNode*> > trees;
          trees.push_back(std::vector<TreeNode*>(1, NULL));
          for (int i=1; i<=n; ++i) {    // Dynamic programming.
            std::vector<TreeNode*> next_trees;
            for (int j=1; j<=i; ++j) {  // Everyone can be the root.
              for (int k=0; k<trees[j-1].size(); ++k) // There're k nodes in left subtree.
                for (int l=0; l<trees[i-j].size(); ++l) {
                  TreeNode * root = new TreeNode(j);
                  root->left = copyTree(trees[j-1][k]);
                  root->right = copyTree(trees[i-j][l], j);
                  next_trees.push_back(root);
                }
            }
            trees.push_back(next_trees);
          }
          for (int i=1; i<trees.size()-1; ++i)
            for (int j=0; j<trees[i].size(); ++j)
              deleteTree(trees[i][j]);
          return trees.back();
        }
      private:
        TreeNode * copyTree(TreeNode * root, int offset = 0) {
          if (!root) return root;
          TreeNode * new_root = new TreeNode(root->val + offset);
          new_root->left = copyTree(root->left, offset);
          new_root->right = copyTree(root->right, offset);
          return new_root;
        }
        void deleteTree(TreeNode * tn) {
          if (!tn) return;
          deleteTree(tn->left);
          deleteTree(tn->right);
          delete tn;
        }
    };

  • 0
    H

    why this is a DP solution? I don't think this solution reflect something like DP.


Log in to reply
 

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