首页 > 代码库 > Unique Binary Search Tree II

Unique Binary Search Tree II

2024-07-17 15:16:15   219人阅读

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 };

 


联系
我们