leetcode-95 Unique Binary Search Trees II

Posted on | In , | |
Words count in article: 384 | Reading time ≈ 2

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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
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
/**
 * 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 <= 0)
            return vector<TreeNode*>();
        return helper(1,n);
    }
    
    vector<TreeNode*> helper(int start, int end){
        if(start > end){
            return {nullptr};
        }
        vector<TreeNode*> res;
        
        for(int i=start; i<=end; i++){
            for(auto leftres: helper(start, i-1))
            {
                for(auto rightres: helper(i+1, end)){
                    TreeNode* node = new TreeNode(i);
                    node->left = leftres;
                    node->right = rightres;
                    res.push_back(node);
                }
            }
        }
        return res;
    }
};

dp:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
 * 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:
    TreeNode* CopyTree(TreeNode* root){
        if(!root) return NULL;
        TreeNode* newroot = new TreeNode(root->val);
        newroot->left = CopyTree(root->left);
        newroot->right = CopyTree(root->right);
        return newroot;
    }
    
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> pre;
        pre.push_back({nullptr});
        
        if(n <= 0) return {};
        
        vector<TreeNode*> cur;
        for(int i=1; i<=n; i++){
            for(TreeNode* node: pre){
                TreeNode* root = new TreeNode(i);
                root->left = node;
                cur.push_back(root);
                TreeNode* temp = node;
                while(temp){
                    TreeNode* newroot = new TreeNode(i);
                    if(temp->right){
                        TreeNode* node_right = temp->right;
                        newroot->left = temp->right;
                        temp->right = newroot;
                        TreeNode* newtree = CopyTree(node);
                        temp->right = node_right;
                        temp = temp->right;
                        cur.push_back(newtree);
                    }
                    else{
                        temp->right = newroot;
                        TreeNode* newtree = CopyTree(node);
                        cur.push_back(newtree);
                        temp->right = nullptr;
                        temp = temp->right;
                    }
                    delete newroot;
                }
            }
            pre = cur;
            cur.clear();
        }
        return pre;
    }
};

Donate? comment?