Unique Binary Search Trees II Problem


Description

LeetCode Problem 95.

Given an integer n, return all the structurally unique BST’s (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in any order.

Example 1:

1
2
Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

Example 2:

1
2
Input: n = 1
Output: [[1]]

Constraints:

  • 1 <= n <= 8


Sample C++ Code

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
43
44
45
46
/* Given a tree which n nodes, it has the follwing form:
(0)root(n-1)
(1)root(n-2)
(2)root(n-3)
where (x) denotes the trees with x nodes.

Now take n=3 for example. Given n=3, we have [1 2 3] in which 
each of them can be used as the tree root.

when root=1: [1 # 2 # 3]; [1 # 3 2];
when root=2: [2 1 3];
when root=3: (similar with the situations when root=1.)

Thus, if we write a recursive function who generates a group of 
trees in which the numbers range from f to t, we have to generate 
the left trees and right trees of each tree in the vector. */
vector<TreeNode *> generateTree(int from, int to)
{
    vector<TreeNode *> ret;
    if(to - from < 0) ret.push_back(0);
    if(to - from == 0) ret.push_back(new TreeNode(from));
    if(to - from > 0)
    {
        for(int i=from; i<=to; i++)
        {
            vector<TreeNode *> l = generateTree(from, i-1);
            vector<TreeNode *> r = generateTree(i+1, to);

            for(int j=0; j<l.size(); j++)
            {
                for(int k=0; k<r.size(); k++)
                {
                    TreeNode * h = new TreeNode (i);
                    h->left = l[j];
                    h->right = r[k];
                    ret.push_back(h);
                }
            }
        }
    }
    return ret;
}

vector<TreeNode *> generateTrees(int n) {
    return generateTree(1, n);
}




Related Posts

Convert Sorted Array to Binary Search Tree Problem

LeetCode 108. Given an integer array nums where the elements...

Validate Binary Search Tree Problem

LeetCode 98. Given the root of a binary tree, determine...

Same Tree Problem

LeetCode 100. Given the roots of two binary trees p...

Recover Binary Search Tree Problem

LeetCode 99. You are given the root of a binary...

Unique Binary Search Trees Problem

LeetCode 96. Given an integer n, return the number of...

Unique Binary Search Trees II Problem

LeetCode 95. Given an integer n, return all the structurally...