95. Unique Binary Search Trees II

Posted on | In | 浏览 次
Words count in article: 530 | Reading time ≈ 2

题目

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n.

Example:

Input: 3
Output:
[
  [1,null,3,2],
  [3,2,null,1],
  [3,1,null,null,2],
  [2,1,3],
  [1,null,2,null,3]
]
Explanation:
The above output corresponds to the 5 unique BST's shown below:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

题解

  • 本题的题意比较简单，给出二叉搜索树的节点数目n，求出可以构成多少中不同结构的二叉搜索树。
  • 其实实现起来还是比较简单的。对于其中一个节点i，将其作为该树的根节点，然后其左边的元素都作为其左子树的元素，右边的元素都作为其右子树的元素，再通过递归得到其左子树和右子树的可能出现的情况的集合，然后再组合起来。一些需要注意的情况：
    • 递归的结束条件： 当该子树的起点大于终点的时候 — start > end，递归结束，能够生成子树的情况为无，即为NULL。
    • 对得到的左子树和右子树的返回情况需要判断其是否为空（可能没有不存在左或右节点的情况)，如果不存在，需要推入一个NULL，然后再进行组合，否则遍历组合的时候left.size * right.size = 0，将导致结果不全，只有左右子树都存在的结果。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
    * Definition for a binary tree node.
    * struct TreeNode {
    *     int val;
    *     TreeNode *left;
    *     TreeNode *right;
    *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };
    */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(!n) 
            return vector<TreeNode*>();
        
        vector<TreeNode*> v = myGenerate(1, n);
        return v;
    }

    vector<TreeNode*> myGenerate(int start, int end) {
        vector<TreeNode*> v;
        if(start > end)	return v;
    
        for(int i = start; i <= end; ++i) {
            vector<TreeNode*> left = myGenerate(start, i-1);
            vector<TreeNode*> right = myGenerate(i + 1, end);
    
            if(!left.size())	left.push_back(NULL);
            if(!right.size())	right.push_back(NULL);
    
            for(int j = 0; j < left.size(); ++j) {				
                for(int k = 0; k < right.size(); ++k) {
                    TreeNode* node = new TreeNode(i);
                    node->left = left[j];
                    node->right = right[k];
                    v.push_back(node);
                }
            }
        }
        return v;	
    }
};