95. Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1 … n.Example:Input: 3Output:[ [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难度：medium题目：给出整数n，生成其所有可能BST.思路：递归，分别把1到n作为根结点，例如i, 则1到i-1作为左子树，i+1到n作为右子树。Runtime: 2 ms, faster than 89.21% of Java online submissions for Unique Binary Search Trees II.Memory Usage: 39.9 MB, less than 100.00% of Java online submissions for Unique Binary Search Trees II./** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public List<TreeNode> generateTrees(int n) { if (n <= 0) { return new ArrayList<TreeNode>(); } return generateTrees(1, n); } private List<TreeNode> generateTrees(int left, int right) { if (left > right) { List<TreeNode> treeNodes = new ArrayList<>(); treeNodes.add(null); return treeNodes; } List<TreeNode> result = new ArrayList<>(); for (int i = left; i <= right; i++) { List<TreeNode> leftList = generateTrees(left, i - 1); List<TreeNode> rightList = generateTrees(i + 1, right); for (TreeNode lChild: leftList) { for (TreeNode rChild: rightList) { TreeNode root = new TreeNode(i); root.left = lChild; root.right = rChild; result.add(root); } } } return result; }}