首页 > 代码库 > LeetCode: Unique Binary Search Trees II [096]
LeetCode: Unique Binary Search Trees II [096]
【题目】
Given n, generate all structurally unique BST‘s (binary search trees) that store values 1...n.
For example,
Given n = 3, your program should return all 5 unique BST‘s shown below.
1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3
confused what "{1,#,2,3}"
means? > read more on how binary tree is serialized on OJ.
【题意】
Unique Binary Search Trees只需要让我们求出可能二叉搜索树的数目,而本题是让我们把这些可能的二叉搜索树都建出来。【思路】
思路和Unique Binary Search Trees完全相同,将原问题分解为求解左右子树所有可能形态的子问题,用递归求解。只不过多了建树的环节。【代码】
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: vector<TreeNode *> getAllBinaryTrees(int start, int end){ vector<TreeNode*> trees; if(start>end){ //注意这里没有等号,Unique Binary Search Trees只是计数,叶子节点和NULL节点都计数为1, 而本题就不一样了,叶子节点作为一棵独立的子树生成。 trees.push_back(NULL); return trees; } for(int k=start; k<=end; k++){ //得到左子树集合 vector<TreeNode*>leftTrees = getAllBinaryTrees(start, k-1); //得到右子树集合 vector<TreeNode*>rightTrees = getAllBinaryTrees(k+1, end); //组合,生成二叉搜索树 for(int l=0; l<leftTrees.size(); l++){ for(int r=0; r<rightTrees.size(); r++){ //创建根节点 TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode)); root->val=k; root->left=leftTrees[l]; root->right=rightTrees[r]; trees.push_back(root); } } } return trees; } vector<TreeNode *> generateTrees(int n) { vector<TreeNode*>result; if(n==0){result.push_back(NULL);return result;} //当n==0时是一棵空树,别忘了 result = getAllBinaryTrees(1, n); return result; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。