给定一个值n,请生成所有的存储值1...n.的二叉搜索树(BST)的结构
例如:
给定n=3,你的程序应该给出下面五种不同的二叉搜索树(BST)
/** * 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; } }
class Solution: def __init__(self): # 使用备忘录存储优化 self.memo = {} def generateTrees(self , n ): if n == 0: return [None] if n == 1: return [TreeNode(1)] # 使用数据范围做递归构树 result = self.built(1, n) # 返回所有结果 return result # 根据范围递归构树 def built(self, start, end): if start > end: return [None] if start == end: return [TreeNode(start)] # 查询是否在备忘录中 if (start, end) in self.memo: return self.memo[(start, end)] # 中间结果 mid = [] # 每个结点做根结点 for i in range(start, end+1): # 选定i作为根,再递归构造所有可能的左右子树 left = self.built(start, i-1) right = self.built(i+1, end) # 构造每一棵树 for l in left: for r in right: root = TreeNode(i) root.left = l root.right = r # 存结果 mid.append(root) # 备忘录存储 self.memo[(start, end)] = mid # 返回结果 return self.memo[(start, end)]
class Solution { public: vector<TreeNode*> generateTrees(int n) { return gen(1, n); } vector<TreeNode*> gen(int l, int r) { if(l > r) return vector<TreeNode*>(1, NULL); if(l == r) { return vector<TreeNode*>(1, new TreeNode(l)); } vector<TreeNode*> vecs; for(int k = l; k <= r; k++) { vector<TreeNode*> vleft = gen(l, k-1); vector<TreeNode*> vright = gen(k+1, r); for(int i = 0; i < vleft.size(); i++) { for(int j = 0; j < vright.size(); j++) { TreeNode *node = new TreeNode(k); node->left = vleft[i]; node->right = vright[j]; vecs.push_back(node); } } } return vecs; } };
后序遍历的变体,先将左右子树的所有搭配方式保存到两个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; } };
vector<TreeNode *> dfs(int l,int r){ vector<TreeNode *>re; for(int i=l;i<=r;i++){ vector<TreeNode *>te1=dfs(l,i-1); vector<TreeNode *>te2=dfs(i+1,r); if(te1.size()==0)te1.push_back(NULL); if(te2.size()==0)te2.push_back(NULL); for(auto j:te1){ for(auto k:te2){ TreeNode* tn=new TreeNode(i); tn->left=j; tn->right=k; re.push_back(tn); } } } return re; } vector<TreeNode *> generateTrees(int n) { vector<TreeNode *>ans; if(n>0)ans=dfs(1,n); else ans.push_back(NULL); return ans; }
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; } }