题目

题解

定义二叉树:

//Definition for a binary tree node.
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    * };

1. 递归法

class Solution {//#96的升级版。两种方法。1、递归
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> ans;
        if(n==0) return ans;//特殊情况的判断，如果n==0返回空数组
        return helper(1,n);
    }

    vector<TreeNode*> helper(int start,int end){
        vector<TreeNode*> res;
        if(start>end){
            res.push_back(nullptr);
            return res;
        }//如果i==start，则start>i-1,此时直接返回null
        if(start==end){
            TreeNode *Tree = new TreeNode(start);
            res.push_back(Tree);
            return res;
        }//此时该子树只有一个值，即只有一个二叉搜索树，直接返回
        for(int i=start;i<=end;i++){
            vector<TreeNode*> leftList = helper(start,i-1);
            vector<TreeNode*> rightList = helper(i+1,end);
            //先建立两个存左右子树情况的数组
            for(auto leftTree:leftList){
                for(auto rightTree:rightList){
                    TreeNode* root = new TreeNode(i);
                    root->left = leftTree;
                    root->right = rightTree;
                    res.push_back(root);
                    //进行排列组合，以i为根节点，组合两边的二叉搜索树情况
                }
            }
        }
        return res;
    }
};

这道题也可以用memo进行优化，代码如下

class Solution {//#96的升级版。两种方法。1.1、递归+memo。用空间换时间
public:
    vector<TreeNode*> generateTrees(int n) {
        vector<TreeNode*> ans;
        if(n==0) return ans;//特殊情况的判断，如果n==0返回空数组
        vector<vector<vector<TreeNode*>>> memo(n,vector<vector<TreeNode*>>(n));//注意memo是三维数组，注意其建立格式
        return helper(1,n,memo);//加入memo的传参
    }

    vector<TreeNode*> helper(int start,int end, vector<vector<vector<TreeNode*>>>& memo){//加入memo传参，注意用引用传参
        vector<TreeNode*> res;
        if(start>end){
            res.push_back(nullptr);
            return res;
        }//如果i==start，则start>i-1,此时直接返回null
        if(start==end){
            TreeNode *Tree = new TreeNode(start);
            res.push_back(Tree);
            return res;
        }//此时该子树只有一个值，即只有一个二叉搜索树，直接返回
        if(!memo[start-1][end-1].empty()) return memo[start-1][end-1];//如果已经递归计算过该start-end的二叉搜索树集合，直接返回结果。
        for(int i=start;i<=end;i++){
            vector<TreeNode*> leftList = helper(start,i-1,memo);
            vector<TreeNode*> rightList = helper(i+1,end,memo);//注意这两句加入了memo参数传递
            //先建立两个存左右子树情况的数组
            for(auto leftTree:leftList){
                for(auto rightTree:rightList){
                    TreeNode* root = new TreeNode(i);
                    root->left = leftTree;
                    root->right = rightTree;
                    res.push_back(root);
                    //进行排列组合，以i为根节点，组合两边的二叉搜索树情况
                }
            }
        }
        memo[start-1][end-1] = res;//将本次计算的res结果存储在memo中
        return res;
    }
};

2. 动态规划法

//占坑

$$ c = \sqrt{a^{2}+b_{0}^{2}+e^{x}} $$