二叉搜索树（三）labuladong学习笔记

文章对应的题目

96 不同的二叉搜索树
95 不同的二叉搜索树II

96.不同的二叉搜索树

96.不同的二叉搜索树

int count(int low, int high);  //闭区间[low, high]的数字能组成count(low, high)种BST

具体实现代码如下：

class Solution {
public:
    int numTrees(int n) {
        return count(1, n);
    }
    int count(int low, int high) {
        if(low > high)
            return 1;
        int res = 0;
        for(int mid = low; mid <= high; mid++) {
            int left = count(low, mid - 1);
            int right = count(mid + 1, high);
            res += left * right;
        }
        return res;
    }
};

提交之后并不能通过，超出时间限制，因为存在重叠子问题，在动态规划中消除重叠子问题的方法，就是加一个备忘录memo。代码如下：

class Solution {
public:
    int numTrees(int n) {
        vector<vector<int>> memo(n, vector<int>(n)); //初始化二维vector，每一个元素都为0
        return count(1, n, memo);
    }
    int count(int low, int high, vector<vector<int>> memo) {
        if(low > high)
            return 1;
        if(memo[low - 1][high - 1] !=0)
            return memo[low - 1][high - 1];
        int res = 0;
        for(int mid = low; mid <= high; mid++) {
            int left = count(low, mid - 1, memo);
            int right = count(mid + 1, high, memo);
            res += left * right;
        }
        memo[low - 1][high - 1] = res;
        return res;
    }
};

但是提交之后还是超过时间限制...

95.不同的二叉搜索树II

此题思路和上题一样，都是遍历每一个节点作为根节点，迭代求出以当前点为根节点其他子树的树的形状。
具体的步骤为：

1. 穷举root节点的所有可能。
2. 递归构造左右子树的BST。
3. 穷举左右子树作为root的左右子树
   具体代码如下

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<TreeNode*> generateTrees(int n) {
        if(n == 0)
            return {};
        return build(1, n);
        
    }
    vector<TreeNode*> build(int low, int high) {
        if(low > high) {
            return {nullptr};
        }
        vector<TreeNode*> res;    //保存当前root节点的结果
        for(int mid = low; mid <= high; mid ++) {
            vector<TreeNode*> left = build(low, mid - 1);
            vector<TreeNode*> right = build(mid + 1, high);
            //给root节点穷举所有所有子树的组合
            for(auto i : left) {
                for(auto j : right) {
                    TreeNode* root = new TreeNode(mid);
                    root -> left = i;
                    root -> right = j;
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};