一.题目

Unique Binary Search Trees II

Total Accepted: 32757 Total Submissions: 117071My Submissions

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.

Show Tags Have you met this question in a real interview? Yes No

Discuss

二.解题技巧

这道题和Unique Binary Search Trees很相似，只是这道题可能无法使用动态规划减少计算的时间，因为每一个节点的值是不一样的，不存在相同的子问题的情况，因此，计算复杂度无法下降。使用递归的方式进行的时候，时间复杂度为O(n^3)，空间复杂度为O(n)。

三.实现代码

#include 
  
   
#include 
   
     #include 
    
      using std::vector; using std::unordered_map; /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { private: unordered_map
     
       > PreResult; vector
      
        generateTrees(int n, int base) { vector
       
         Result; if (n == 0) { TreeNode* TmpNode = NULL; Result.push_back(TmpNode); return Result; } if (n == 1) { TreeNode* TmpNode = new TreeNode(n + base); Result.push_back(TmpNode); return Result; } for (int HeadIndex = 1; HeadIndex <= n; HeadIndex++) { vector
        
          LeftChildVector = generateTrees(HeadIndex - 1, base); vector
         
           RightChildVector = generateTrees(n - HeadIndex, base + HeadIndex); const vector
          
           ::size_type LEFTSIZE = LeftChildVector.size(); const vector
           
            ::size_type RIGHTSIZE = RightChildVector.size(); for (vector
            
             ::size_type IndexOfLeft = 0; IndexOfLeft < LEFTSIZE; IndexOfLeft++) { for (vector
             
              ::size_type IndexOfRight = 0; IndexOfRight < RIGHTSIZE; IndexOfRight++) { TreeNode *TmpHeadNode = new TreeNode(base + HeadIndex); TmpHeadNode->left = LeftChildVector[IndexOfLeft]; TmpHeadNode->right = RightChildVector[IndexOfRight]; Result.push_back(TmpHeadNode); } } } return Result; } public: vector
              
                generateTrees(int n) { return generateTrees(n, 0); } };

四.体会

这道题也是一个和Unique Binary Search Trees类似的问题，解题思路也比较类似，只是这个的返回是所有可能的二叉查找树，主要解答过程只是稍微修改下即可。

?

LeetCode_Unique Binary Search Trees II

一.题目

Unique Binary Search Trees II

二.解题技巧

三.实现代码

四.体会