LeetCode 95.Unique Binary Search Trees II

xiaoxiao2021-02-28  5

LeetCode 95.Unique Binary Search Trees II

题目链接:https://leetcode.com/problems/unique-binary-search-trees-ii/description/

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

这道题是求解所有可行的二叉查找树,在Unique Binary Search Trees中,二叉查找树的数目是卡塔兰数,在上一题中我们采用的方法存储所有子问题的解,存储G(1)…G(n-1),再求解G(n),如此题采用这种方式会浪费很多空间,因此我们采用循环中调用递归函数求解子问题。思路是:每次选取一个结点作为根,然后递归求解左右子树的结果,然后将左右子树的结果进行匹配,若左子树有p种,右子树有q种,则以i为根的BST有p*q种,将每个结点作为根的所有结果都加入集合后,再返回结果。

/** * 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; } }
转载请注明原文地址: https://www.6miu.com/read-1750270.html

最新回复(0)