首页 > 代码库 > LeetCode:Unique Binary Search Trees II
LeetCode: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
思路分析:分别让1-n做root。当root为i时,左子树由1~i-1组成,右子树由i+1~n组成。采用递归的方法分别对左右子树求解,再将左右子树所有可能的解组合在一起,即可得到所有可能的BST。
代码:
vector<TreeNode *> getTrees(int start,int end) { vector<TreeNode *> result; if(start > end) { result.push_back(NULL); return result; } if(start == end) { TreeNode * new_node = new TreeNode(start); result.push_back(new_node); return result; } for(int i = start;i <= end ;i++) { vector<TreeNode *> left = getTrees(start,i-1); vector<TreeNode *> right = getTrees(i+1,end); for(TreeNode * left_node:left) for(TreeNode * right_node:right) { TreeNode * new_node = new TreeNode(i); new_node->left = left_node; new_node->right = right_node; result.push_back(new_node); } } return result; } vector<TreeNode *> Solution::generateTrees(int n) { return getTrees(1,n); }
LeetCode:Unique Binary Search Trees II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。