generateTrees.cpp

#include <vector>
#include <iostream>
#include <unordered_map>

#define _DEBUG

// 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 (binary search trees)  shown below:
//
//    1         3     3      2      1
//     \       /     /      / \      \
//      3     2     1      1   3      2
//     /     /       \                 \
//    2     1         2                 3
//

using namespace std;

// 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) {
        vector<int> array{};

        for (int i = 0; i < n; i++) {
            array.push_back(i+1);
        }

        return doit(array, 0);
    }

    void dump(TreeNode *root) {
#ifdef _DEBUG
        cout << "[";
        cout << root->val << ",";
        _dump(root);
        cout << "]" << endl;
#endif
    }

    void _dump(TreeNode *root) {

        if (root->left != NULL || root->right != NULL) {
            if (root->left != NULL) {
                cout << root->left->val << ",";
            } else {
                cout << "NULL,";
            }
            if (root->right != NULL) {
                cout << root->right->val << ",";
            } else if (root->left != NULL && root->left->left == NULL && root->left->right == NULL ) {
            } else {
                cout << "NULL,";
            }
        }

        if (root->left != NULL)
            _dump(root->left);
        if (root->right != NULL)
            _dump(root->right);
    }

    void indent(int depth) {
        for (int i = 0; i < depth; i++)
            cout << "  ";
    }

    vector<TreeNode*> doit(vector<int> array, int depth) {

        if (array.size() == 2) {
            // case 1
            auto p1 = new TreeNode(array[0]);
            auto p2 = new TreeNode(array[1]);
            p2->left = p1;

            // case 2
            auto p3 = new TreeNode(array[0]);
            auto p4 = new TreeNode(array[1]);
            p3->right = p4;
            
#ifdef _DEBUG
            indent(depth);
            cout << "list - 2 - " << endl;
#endif

            return vector<TreeNode*>{p2, p3};
        } else if (array.size() == 1) {
            auto p1 = new TreeNode(array[0]);
#ifdef _DEBUG
            indent(depth);
            cout << "list - 1 - " << endl;
#endif
            return vector<TreeNode*>{p1};
        } else {
            vector<TreeNode*> list{};
            for (int i = 0; i < array.size(); i++) {
#ifdef _DEBUG
                indent(depth);
                cout << "current "  << array[i] << "/" << array.size() << endl;
#endif
                vector<int> gt{};
                vector<int> lt{};
                for (int j = 0; j < array.size(); j++) {
                    if (array[i] > array[j]) {
                        lt.push_back(array[j]);
                    } else if (array[i] < array[j]) {
                        gt.push_back(array[j]);
                    }
                }

#ifdef _DEBUG
                indent(depth);
                cout << "gt "  << gt.size() << endl;
                indent(depth);
                cout << "lt "  << lt.size() << endl;
#endif

                auto gt_array = doit(gt, depth + 1);
                auto lt_array = doit(lt, depth + 1);

                int count = list.size();

                if (gt_array.size() > 0 && lt_array.size() == 0) {
                    auto it_gt = gt_array.begin();
                    while(it_gt != gt_array.end()) {
                        auto root = new TreeNode(array[i]);
                        root->right = *it_gt;
                        list.push_back(root);
                        dump(root);
                        it_gt++;
                    }
                } else if (lt_array.size() > 0 && gt_array.size() == 0) {
                    auto it_lt = lt_array.begin();
                    while(it_lt != lt_array.end()) {
                        auto root = new TreeNode(array[i]);
                        root->left = *it_lt;
                        list.push_back(root);
                        dump(root);
                        it_lt++;
                    }
                } else {
                    auto it_gt = gt_array.begin();
                    while(it_gt != gt_array.end()) {
                        auto it_lt = lt_array.begin();
                        while(it_lt != lt_array.end()) {
                            auto root = new TreeNode(array[i]);
                            root->right = *it_gt;
                            root->left = *it_lt;
                            list.push_back(root);
                            it_lt++;
                        }
                        it_gt++;
                    }
                }

#ifdef _DEBUG
                indent(depth);
                cout << "gt_array "  << gt_array.size() << endl;
                indent(depth);
                cout << "lt_array "  << lt_array.size() << endl;
                indent(depth);
                cout << "incomming " << list.size() - count << endl;
#endif

            }
#ifdef _DEBUG
            indent(depth);
            cout << "list " << list.size() << "/" << array.size() << endl;
#endif
            return list;
        }
    }
};

int test(int n) {
    auto obj = Solution();
    auto a = obj.generateTrees(n);
    auto it = a.begin();
    while (it != a.end()) {
        obj.dump(*it);
        it++;
    }
    cout << a.size() << endl;
    return a.size();
}

int main(int argc, char**argv) {

    assert(test(3) == 5);
    assert(test(4) == 14);
    assert(test(5) == 42);

    return 0;
}