lc95-Unique Binary Search Trees II

發表於   |   分類於   |   0 comments   |   
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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 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<vector<TreeNode*>> forests;
    int max = -1;
    TreeNode* traversalAdd(int n, TreeNode* tree) {
        if (tree == NULL) return NULL;
        TreeNode* root = new TreeNode(tree->val + n);
        root -> left = traversalAdd(n, tree -> left);
        root -> right = traversalAdd(n, tree -> right);
        return root;
    }
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> resultTrees;
        if (n > max) {
            vector<TreeNode*> trees;
            for (int i = 0; i < n + 1; i++)
                forests.push_back(trees);
            max = n;
        }
        if (forests[n].size() == 0 && n != 0){
            if (n == 1) {
                TreeNode *root = new TreeNode(1);
                forests[1].push_back(root);
                return forests[1];
            }
            if (n == 0) {
                //forests[0].push_back(NULL);
                return forests[0];
            }
            
            // vector<TreeNode*> left;
            // left.push_back(NULL);
            vector<TreeNode *> right = generateTrees(n - 1);
            for (int k = 0; k < right.size(); k++) {
                TreeNode *root = new TreeNode(1);
                root -> left = NULL;
                root -> right = traversalAdd(1, right[k]);
                resultTrees.push_back(root);
            }
                
            for (int i = 1; i < n - 1; i++) {
                vector<TreeNode *> left = generateTrees(i);
                vector<TreeNode *> right = generateTrees(n - 1 - i);
                for (int j = 0; j < left.size(); j++) {
                    for (int k = 0; k < right.size(); k++) {
                        TreeNode *root = new TreeNode(i + 1);
                        root -> left = left[j];
                        root -> right = traversalAdd(i + 1, right[k]);
                        resultTrees.push_back(root);
                    }
                }
            }
            
            // right.clear();
            // right.push_back(NULL);
            vector<TreeNode*> left = generateTrees(n - 1);
            for (int k = 0; k < left.size(); k++) {
                TreeNode *root = new TreeNode(n);
                root -> left = left[k];
                root -> right = NULL;//right;
                resultTrees.push_back(root);
            }
            
            return resultTrees;
        }
        else return forests[n];
    }
};