不同的二叉搜索树 ii

/**
 * Definition for binary tree
 * 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) {
        if (n <= 0) return helper(1, 0);
        return helper(1,n);
    }
private:
    vector<TreeNode*> helper(int start,int end)
    {
        vector<TreeNode*> subTree;
        if(start>end) 
        {
            subTree.push_back(nullptr);
            return subTree;
        }
        for (int k = start; k <= end; k++) 
        {
           vector<TreeNode*> leftSubs = helper(start, k - 1);
           vector<TreeNode*> rightSubs = helper(k + 1, end);
           for (auto i : leftSubs) 
           {
              for (auto j : rightSubs) 
              {
                TreeNode *node = new TreeNode(k);
                node->left = i;
                node->right = j;
                subTree.push_back(node);
              }
            }
        }
        return subTree;
        
    }       
};

import java.util.*;
public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
		return createTree(1, n);
	}
	public ArrayList<TreeNode> createTree(int low, int high) {
		ArrayList<TreeNode> result = new ArrayList<>();
		if(low > high) {
			result.add(null);
			return result;
		}
		for (int i = low; i <= high; i ++) {
			// 求根结点i的左右子树集合
			ArrayList<TreeNode> left = createTree(low, i - 1);
			ArrayList<TreeNode> right = createTree(i + 1, high);
			for (int j = 0; j < left.size(); j ++) {
				for (int k = 0; k < right.size(); k ++) {
					// 将左右子树相互配对，每一个左子树都与所有右子树匹配，每一个右子树都与所有的左子树匹配
					TreeNode newNode = new TreeNode(i);
					newNode.left = left.get(j);
					newNode.right = right.get(k);
					result.add(newNode);
				}
			}
		}
		return result;
	}
}

class Solution {
public:
    //递归创建
    vector<TreeNode *> creatTrees(int left,int right){
        vector<TreeNode *> res;
        if(left>right){
            res.push_back(NULL);
            return res;
        }
        for(int i=left;i<=right;i++){ //以i为根节点的树，其左子树由[1, i-1]构成， 其右子树由[i+1, n]构成。该原则建树具有唯一性
            vector<TreeNode *> left_res = creatTrees(left,i-1);
            vector<TreeNode *> right_res = creatTrees(i+1,right); 
            //每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况
            int lsize = left_res.size();
            int rsize = right_res.size();
            for(int j=0;j<lsize;j++){
                for(int k=0;k<rsize;k++){
                    TreeNode *root = new TreeNode(i);
                    root->left = left_res[j];
                    root->right = right_res[k];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
    vector<TreeNode *> generateTrees(int n) {
        //本题主要考察二叉排序树的构建
        //unique-binary-search-trees-i，我们可以知道结果的数目是一个卡特兰数列，当本题需要把所有可能的二叉排序
        //给构建出来要求解所有的树，自然是不能多项式时间内完成的思路是每次一次选取一个结点为根，然后递归求解左右子树的所有结果，最后根据左右子树的返回的所有子树，依次选取
        //然后接上（每个左边的子树跟所有右边的子树匹配，而每个右边的子树也要跟所有的左边子树匹配，总共有左右子树数量的乘积种情况），构造好之后作为当前树的
        //结果返回
        return creatTrees(1,n);  //从1作为root开始，到n作为root结束
    }
};

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        return Create(1,n);
    }
    vector<TreeNode *> Create(int l,int r)
    {
    	vector<TreeNode *> result,L,R;
    	if(l>r)
    		result.push_back(NULL);
    	else if(l == r){
			TreeNode *root = new TreeNode(l);
			result.push_back(root);
			return result;
		}
		for(int i=l;i<=r;i++)
		{
			L = Create(l,i-1);
			R = Create(i+1,r);
			for(int j=0;j<L.size();j++)
				for(int k=0;k<R.size();k++)
				{
					TreeNode *root = new TreeNode(i);
					root->left = L[j];
					root->right = R[k];
					result.push_back(root);
				}
		}
    	return result;
	}
};

public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        ArrayList<TreeNode>[] res = new ArrayList[n + 1];
        
		res[0] = new ArrayList<TreeNode>();
		if (n <= 0){
            res[0].add(null);
            return res[0];
        }
			
		// 必须add(null)，否则for (TreeNode left : res[0])
		res[0].add(null);
		for (int i = 1; i <= n; i++) {
			res[i] = new ArrayList<TreeNode>();
			for (int j = 1; j <= i; j++) {
				for (TreeNode left : res[j - 1]) {
					for (TreeNode right : res[i - j]) {
						TreeNode node = new TreeNode(j);
						node.left = left;
						node.right = clone(right, j);
						res[i].add(node);
					}
				}
			}
		}
		return res[n];
	}

	private TreeNode clone(TreeNode n, int offset) {
		if (n == null)
			return null;
		TreeNode node = new TreeNode(n.val + offset);
		node.left = clone(n.left, offset);
		node.right = clone(n.right, offset);

		return node;
	}
    
}

    /*
    * 目的：构建BST，相当于平衡二叉搜索树的拓展
    * 方法：递归，跟回溯法差不多，傻傻分不清楚
    */
    vector<TreeNode*>generateTreesCore(int start, int end){
        vector<TreeNode *> res;
        if(start > end){
            res.push_back(nullptr);
            return res;
        }
        for(int k = start; k <= end; ++k){
            vector<TreeNode *> left = generateTreesCore(start, k-1);
            vector<TreeNode *> right = generateTreesCore(k+1, end);
            for(int i = 0; i < left.size(); ++i){
                for(int j = 0; j < right.size(); ++j){
                    TreeNode* root = new TreeNode(k);
                    root->left = left[i];
                    root->right = right[j];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
    vector<TreeNode *> generateTrees(int n) {
        return generateTreesCore(1,n);
    }

https://yq.aliyun.com/articles/3692

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
        if(n <= 0){
            return helper(1,0);
        }else{
            return helper(1,n);
        }
    }
    vector<TreeNode *> helper(int start, int end){
        vector<TreeNode *> subTree;
        if(start > end){
            subTree.push_back(NULL);
        }else{
            for(int i = start ; i <= end ; ++i){
                vector<TreeNode *> left = helper(start,i-1);
                vector<TreeNode *> right = helper(i+1,end);
                for(int j = 0 ; j != left.size() ; ++j){
                    for(int z = 0 ; z != right.size(); ++z){
                        TreeNode *subRoot = new TreeNode(i);
                        subRoot->left = left[j];
                        subRoot->right = right[z];
                        subTree.push_back(subRoot);
                    }
                }
            }
        }
        return subTree;
    }
};

class Solution {
public:
    vector<TreeNode *> generateTrees(int n) {
          return dfs(1,n);
    } 
    vector<TreeNode *> dfs(int l,int r){
          vector<TreeNode*> ans;
          if(l>r) {ans.push_back(NULL);return ans;}
          for(int i=l;i<=r;i++){
              vector<TreeNode*> vecl=dfs(l,i-1),vecr=dfs(i+1,r);
              for(auto p:vecl)
                  for(auto q:vecr){
                      TreeNode *root=new TreeNode(i);
                      root->left=p;
                      root->right=q;
                      ans.push_back(root);
                  }
          }
          return ans;
    }
};

class Solution {
public:
   
 /**
输出1-n组成的所有二叉搜索树的结构,主要思路是选定1-n的一个数字i作为根节点，0~(i-1)做左子树，
                                                                             (i+1)~n做右子树,左右进行组合，两层循环
**/
vector<TreeNode *> dfs(int left,int right)
{
    vector<TreeNode *> res;
    if(left>right)
    {
        res.push_back(nullptr);
        return res;
    }
    for(int i=left;i<=right;i++)
    {
        vector<TreeNode *>leftTree = dfs(left,i-1);
        vector<TreeNode *>rightTree = dfs(i+1,right);
        for(int j=0;j<leftTree.size();j++)
        {
            for(int k=0;k<rightTree.size();k++)
            {
                TreeNode *root = new TreeNode(i);
                root->left = leftTree[j];
                root->right = rightTree[k];
                res.push_back(root);
            }
        }
    }
    return res;
}
vector<TreeNode *> generateTrees(int n)
{
   return dfs(1,n);
}
};

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param n int整型 
     * @return TreeNode类ArrayList
     */
    public ArrayList<TreeNode> generateTrees (int n) {
        // write code here
        return this.dfs(1,n);
    }
    
    private ArrayList<TreeNode> dfs(int left, int right){
        ArrayList<TreeNode> result = new ArrayList<>();
        if(left >right){
            result.add(null);
            return result;
        }
        for(int i=left;i<=right;i++){
            ArrayList<TreeNode> leftNodes = this.dfs(left, i - 1);
            ArrayList<TreeNode> rightNodes = this.dfs(i+1, right);
            for(TreeNode leftNode:leftNodes){
                for(TreeNode rightNode:rightNodes){
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    result.add(root);
                }
            }
        }
        
        return result;
    }
}

后序遍历的变体，先将左右子树的所有搭配方式保存到两个vector，然后再用根节点分别与左右子树搭配：

//
// Created by jt on 2020/8/23.
//
#include 
using namespace std;
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return TreeNode类vector
     */
    vector generateTrees(int n) {
        // write code here
        return postOrder(1, n);
    }
    vector postOrder(int left, int right) {
        vector res;
        if (left > right) return vector{nullptr};
        for (int i = left; i <= right; ++i) {
            vector leftVec = postOrder(left, i-1);
            vector rightVec = postOrder(i+1, right);
            for (int j = 0; j < leftVec.size(); j++) {
                for (int k = 0; k < rightVec.size(); k++) {
                    // 根节点建立必须在循环内部
                    TreeNode *root = new TreeNode(i);
                    root->left = leftVec[j];
                    root->right = rightVec[k];
                    res.push_back(root);
                }
            }
        }
        return res;
    }
};

public class Solution {
    public ArrayList<TreeNode> generateTrees(int n) {
        return helper(1, n);
    }
    public ArrayList<TreeNode> helper(int start, int end){
        ArrayList<TreeNode> result = new ArrayList<TreeNode>();
        if(start > end){
            result.add(null);
        };
        for(int i = start; i <= end; i++){
            ArrayList<TreeNode> leftArr = helper(start, i - 1);
            ArrayList<TreeNode> rightArr = helper(i + 1, end);
            for(TreeNode leftNode : leftArr){
                for(TreeNode rightNode : rightArr){
                    TreeNode root = new TreeNode(i);
                    root.left = leftNode;
                    root.right = rightNode;
                    result.add(root);
                }
            }
        }
        return result;
    }
}