首页 > 代码库 > leetcode -day28 Unique Binary Search Trees I II
leetcode -day28 Unique Binary Search Trees I II
1、
Unique Binary Search Trees II
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
分析:本题很容易想到用递归的方法,依次将每个点作为根结点,然后递归左右子树,但是在这个递归中有个问题,如何判断递归结束,如何保留上层的结点,如何判断递归的是左子树还是有子树,递归的写法还是很重要的。本题中,采用每次先求得下层子树左右子树的结点,然后根据左右子树的不同情况形成不同的树,保存这些树的根结点。
代码如下:
class Solution { public: vector<TreeNode *> generateTrees(int n) { return constructTree(0,n-1); } vector<TreeNode*> constructTree(int startIndex, int endIndex){ vector<TreeNode *> result; //保存下一层的结点 if(startIndex > endIndex){ result.push_back(NULL); return result; } for(int i=startIndex; i<=endIndex; ++i){ vector<TreeNode*> leftTrees = constructTree(startIndex,i-1); vector<TreeNode*> rightTrees = constructTree(i+1,endIndex); for(int j=0; j<leftTrees.size(); ++j){ for(int k=0; k<rightTrees.size(); ++k){ TreeNode * newNode = new TreeNode(i+1); result.push_back(newNode); newNode->left = leftTrees[j]; newNode->right = rightTrees[k]; } } } return result; } };
2、Unique Binary Search Trees
Given n, how many structurally unique BST‘s (binary search trees) that store values 1...n?
For example,
Given n = 3, there are a total of 5 unique BST‘s.
1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3
分析:先做上面的题,后面这个题就简单了,采用递归,每次计算下层的左子树和右子树的数目,本层的不同树的个数为左子树的数目与右子树的数目相乘,每种不同的情况相加即可。
class Solution { public: int numTrees(int n) { if(n < 1){ return 1; } return numTrees(1,n); } int numTrees(int startIndex, int endIndex){ int num = 1; if(startIndex > endIndex){ return num; } num = 0; for(int i=startIndex; i<=endIndex; ++i){ int leftNum = numTrees(startIndex,i-1); int rightNum = numTrees(i+1,endIndex); num += leftNum * rightNum; } return num; } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。