给定一个值n,请生成所有的存储值1...n.的二叉搜索树(BST)的结构
例如:
给定n=3,你的程序应该给出下面五种不同的二叉搜索树(BST)
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; } }
public class Solution { public List<TreeNode> generateTrees(int n) { return genTrees(1,n); } public List<TreeNode> genTrees (int start, int end) { List<TreeNode> list = new ArrayList<TreeNode>(); if(start>end) { list.add(null); return list; } if(start == end){ list.add(new TreeNode(start)); return list; } List<TreeNode> left,right; for(int i=start;i<=end;i++) { left = genTrees(start, i-1); right = genTrees(i+1,end); for(TreeNode lnode: left) { for(TreeNode rnode: right) { TreeNode root = new TreeNode(i); root.left = lnode; root.right = rnode; list.add(root); } } } return list; } }