LeetCode 95.Unique Binary Search Trees II

xiaoxiao2021-02-28  5

LeetCode 95.Unique Binary Search Trees II

Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.

For example, Given n = 3, your program should return all 5 unique BST’s shown below.

1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3

/** * 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<1) return new ArrayList<>(); return CreateBST(1, n); } public List<TreeNode> CreateBST(int left,int right){ List<TreeNode> res=new ArrayList<>(); if(left>right){ res.add(null); //加入一棵空树； return res; } for(int i=left;i<=right;i++){ //i代表以i为根的BST List<TreeNode> leftList=CreateBST(left,i-1); //存储左子树 List<TreeNode> rightList=CreateBST(i+1,right); //存储右子树 for(int j=0;j<leftList.size();j++){ for(int k=0;k<rightList.size();k++){ TreeNode root=new TreeNode(i); root.left=leftList.get(j); root.right=rightList.get(k); res.add(root); } } } return res; } }