Sinh tất cả cây BST duy nhất II trong C++

Cho một số nguyên n, hãy sinh tất cả các cây tìm kiếm nhị phân (BST) cấu trúc duy nhất lưu trữ giá trị từ 1 đến n. Ví dụ n = 3 cho 5 cây như hình:

Giải pháp dùng đệ quy sinh cây:

• Định nghĩa hàm generate(low, high) trả về vector<TreeNode*>
• Nếu low > high, trả về vector chứa NULL
• Với i từ low đến high:
  • left_subtree := generate(low, i-1)
  • right_subtree := generate(i+1, high)
  • Với mỗi cặp (left, right) từ hai vector con:
    • Tạo nút mới với giá trị i
    • Gán left và right
    • Thêm vào kết quả
• Gọi generate(1, n) ban đầu

Ví dụ (C++):

Xem triển khai sau để hiểu rõ hơn:

#include <bits/stdc++.h> 
using namespace std; 

class TreeNode{ 
public: 
    int val; 
    TreeNode *left, *right; 
    TreeNode(int data){ 
        val = data; 
        left = right = NULL; 
    } 
}; 

// ... (các hàm hỗ trợ insert, make_tree, tree_level_trav) 

class Solution { 
public: 
    vector<TreeNode*> generate(int low, int high) { 
        vector<TreeNode*> temp; 
        if(low > high){ 
            temp.push_back(NULL); 
            return temp; 
        } 
        for(int i = low; i <= high; i++){ 
            vector<TreeNode*> leftSubtree = generate(low, i-1); 
            vector<TreeNode*> rightSubtree = generate(i+1, high); 
            for(int j = 0; j < leftSubtree.size(); j++){ 
                for(int k = 0; k < rightSubtree.size(); k++){ 
                    TreeNode* currentNode = new TreeNode(i); 
                    currentNode->left = leftSubtree[j]; 
                    currentNode->right = rightSubtree[k]; 
                    temp.push_back(currentNode); 
                } 
            } 
        } 
        return temp; 
    } 
    
    vector<TreeNode*> generateTrees(int n) { 
        if(!n){ 
            vector<TreeNode*> r; 
            return r; 
        } 
        return generate(1, n); 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<TreeNode*> v = ob.generateTrees(3); 
    for(int i = 0; i < v.size(); i++) 
        tree_level_trav(v[i]); 
    return 0;
}

Đầu vào

3

Đầu ra

[1, 2, 3, ] [1, 3, 2, ] [2, 1, 3, ] [3, 1, 2, ] [3, 2, 1, ]