EEPW论坛

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.

The serialization of a binary tree follows a level order traversal, where '#' signifies a path terminator where no node exists below.

Here's an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as"{1,2,3,#,#,4,#,#,5}".

题意：输出1到n组成的所有二叉搜索树的结构

思路：

选定1-n的一个数字i作为根节点、0到i-1是左子树， i+1-n是右子树，两层循环；

1. class Solution  

2. {  

3. public:  

4.     vector<TreeNode*> generateTrees(int n)  

5.     {  

6.         return create(1, n);  

7.     }  

8.   

9.     vector<TreeNode*> create(int left, int right)  

10.     {  

11.         vector<TreeNode*> res;  

12.         if (left>right)  

13.         {  

14.             res.push_back(NULL);  

15.             return res;  

16.         }  

17.   

18.         for (int i=left; i<=right; i++)  

19.         {  

20.             vector<TreeNode*> leftTree = create(left, i-1);  

21.             vector<TreeNode*> rightTree = create(i+1, right);  

22.   

23.             for (int j = 0; j<leftTree.size(); j++)  

24.             {  

25.                 for (int k = 0; k<rightTree.size(); k++)  

26.                 {  

27.                     TreeNode* root = new TreeNode(i);  

28.                     root->left = leftTree[j];  

29.                     root->right = rightTree[k];  

30.   

31.                     res.push_back(root);  

32.                 }  

33.             }  

34.         }  

35.   

36.         return res;  

37.     }  

38. };