首页 > 代码库 > Unique Binary Search Trees II
Unique Binary Search Trees II
这题首先要明白的是，二叉搜索树的左子树和右子树都自成二叉搜索树。这种递归定义决定了，如果我知道从1到n - 1时，所有的二叉搜索树结构，那结点数为n的二叉搜索树也可以得到了。
转换关系是这样的：
对于一个含有n个结点的二叉搜索树，首先树根可以从i = 1~n变化，然后左右子树的结点数目分别是i - 1和 n- i。
这样分析下来，动态规划的思路就比较明显了。这题麻烦点的是对于一颗树的复制.
TreeNode *copyTree(TreeNode *root, int offSet){ if (root == nullptr) return nullptr; TreeNode *nRoot = new TreeNode(root->val + offSet); nRoot->left = copyTree(root->left, offSet); nRoot->right = copyTree(root->right, offSet); return nRoot;} vector<TreeNode *> generateTrees(int n) { vector<TreeNode *> result; if (n == 0){ result.push_back(nullptr); return result; } vector<vector<TreeNode*> > table(n + 1); TreeNode *t1 = new TreeNode(1); table[0] = {nullptr}; table[1] = {t1}; for (int i = 2; i < n + 1; i++){ vector<TreeNode*> row; for (int j = 1; j < i + 1; j++){ //vector<TreeNode*> lt = table[j - 1];//left: no offset //vector<TreeNode*> rt = table[i - j];//right: offset by j for (auto lIt = table[j - 1].begin(); lIt != table[j - 1].end(); lIt++){ for (auto rIt = table[i - j].begin(); rIt != table[i - j].end(); rIt++){ TreeNode *midNode = new TreeNode(j); midNode->left = copyTree(*lIt, 0); midNode->right = copyTree(*rIt, j); row.push_back(midNode); } } } table[i] = row; } return table[n]; }
Unique Binary Search Trees II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。