分治---不同的二叉搜索树

灰太狼 2021-11-29 07:54 185阅读 0赞

### 不同的二叉搜索树 ###

[95. Unique Binary Search Trees II (Medium)][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; }

转载于:https://www.cnblogs.com/yjxyy/p/11107373.html

[95. Unique Binary Search Trees II _Medium]: https://leetcode.com/problems/unique-binary-search-trees-ii/description/