首页 > 代码库 > Unique Binary Search Tree II
Unique Binary Search Tree 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
分析:这道题与unique binary search tree I不同在于我们要生成所以的二叉查找树并返回树的根。同样我们用递归的方法,如果是空树我们加入一个NULL指针,这个对于简化代码是有帮助的。
如果在空树的情况是我们不加入NULL,而是让<TreeNode *> res为空,那么在通过左右两个子树组成新树时,代码会繁琐很多。因为我们必须要处理左子树、右子树是否为空总共四种情况。
1 class Solution { 2 public: 3 vector<TreeNode *> generateTrees(int n) { 4 vector<TreeNode *> res; 5 res = generateBST(1,n); 6 return res; 7 } 8 vector<TreeNode *> generateBST(int left, int right){ 9 vector<TreeNode *> res;10 if(left > right){11 res.push_back(NULL);12 return res;13 }14 for(int i = left; i <= right; i++){15 vector<TreeNode *> lefts = generateBST(left, i-1);16 vector<TreeNode *> rights = generateBST(i+1,right);17 for(auto k:lefts)18 for(auto j:rights){19 TreeNode * root = new TreeNode(i);20 root->left = k;21 root->right = j;22 res.push_back(root);23 }24 }25 return res;26 }27 };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。