分治---不同的二叉搜索树
不同的二叉搜索树
95. Unique Binary Search Trees II (Medium)
给定一个数字 n，要求生成所有值为 1…n 的二叉搜索树。
Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
题目描述：
给定一个数字n，要求生成所有值为1….n的二叉搜索树。
思路分析：
二叉树有个性质，就是左子树的节点值都比根小，右子树的节点值都比根大，题目说明二叉树的节点值是从1到n，所以我们能够确定如果根为k，那么左子树的值是1到k-1，右子树的值是k+1到n。还有一点是，对于一个根来说，唯一二叉树的数量是其左子树的数量乘上右子树的数量，这是简单的乘法原理。并且左右子树的形态数量跟具体的数没有关系，只跟这个树里有多少个节点有关。而根可以选择从1到n的任意数，唯一二叉树的总数，就是根为1到n的树相加。
代码：
public List<TreeNode>generateTrees(int n){ if(n<1) return new LinkedList<TreeNode>(); return generateSubtrees(1,n); } public List<TreeNode>generateSubtrees(int s,int e){ List<TreeNode>res=new LinkedList<>(); if(s>e){ res.add(null); return res; } for(int i=s;i<=e;++i){ List<TreeNode>leftSubtrees=generateSubtrees(s,i-1); List<TreeNode>rightSubtrees=generateSubtrees(i+1,e); for(TreeNode left:leftSubtrees){ for(TreeNode right:rightSubtrees){ TreeNode root=new TreeNode(i); root.left=left; root.right=right; res.add(root); } } } return res; }
转载于
//www.cnblogs.com/yjxyy/p/11107373.html
╰半橙微兮°
我会带着你远行
不念不忘少年蓝@
今天药忘吃喽~
红太狼
灰太狼
还没有评论，来说两句吧...