Unique Binary Search Trees (leetcode) 动态规划

有多少种不同的二叉搜索树？

动态规划问题

Unique Binary Search Trees

题目地址 https://leetcode.com/problems/unique-binary-search-trees/

可以以其中一个数为根节点，左右两边分开，如此递推

ac代码

class Solution { public: int numTrees(int n) { if (n < 3) return n; vector<int> nums(n+1); nums[0] = 1; nums[1] = 1; nums[2] = 2; for (int i = 3; i <= n; i++){ int cnt = 0; for (int j = 1; j <= i; j++){ cnt += nums[j - 1] * nums[i - j]; } nums[i] = cnt; } return nums[n]; } };

95. Unique Binary Search Trees II

题目地址 https://leetcode.com/problems/unique-binary-search-trees-ii/

ac代码

/** * 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*> vnode(int left, int right){ vector<TreeNode*> ans; if (left > right){ return ans; } else if (left == right){ TreeNode* root = new TreeNode(left); ans.push_back(root); return ans; } else if (left + 1 == right){ TreeNode* root1 = new TreeNode(left); root1->right = new TreeNode(right); TreeNode* root2 = new TreeNode(right); root2->left = new TreeNode(left); ans.push_back(root1); ans.push_back(root2); return ans; } else{ for (int i = left; i <= right; i++){ vector<TreeNode*> vLeft = vnode(left, i - 1); vector<TreeNode*> vRgiht= vnode(i + 1, right); int len1 = vLeft.size(); int len2 = vRgiht.size(); if (len1 == 0){ for (int j = 0; j < len2; j++){ TreeNode* root = new TreeNode(i); root->right = vRgiht[j]; ans.push_back(root); } } else if (len2 == 0){ for (int j = 0; j < len1; j++){ TreeNode* root = new TreeNode(i); root->left = vLeft[j]; ans.push_back(root); } } else{ for (int j = 0; j < len1; j++) { for (int k = 0; k < len2; k++){ TreeNode* root = new TreeNode(i); root->left = vLeft[j]; root->right = vRgiht[k]; ans.push_back(root); } } } } // end for return ans; } } vector<TreeNode*> generateTrees(int n) { vector<TreeNode*> ans; if (n <= 0) return ans; ans = vnode(1, n); return ans; } };