本文共 2194 字，大约阅读时间需要 7 分钟。

题目一：

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?For example,Given n = 3, there are a total of 5 unique BST's.   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3

思路：

建立count[]数组，存放从1到n每一个数对应的BST的个数。

实现代码如下：

public class Solution {
       public int numTrees(int n) {        int[] count = new int[n+1];        count[0] = 1;        for (int i = 1; i <= n; i++) {            for (int root = 1; root <= i; root++) {                int left = count[root-1];                int right = count[i-root];                count[i] += left*right;            }        }        return count[n];    }}Unique Bin

题目二：

Given 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; } * } */public class Solution {
       public List
   
     generateTrees(int n) {        if(n<1){            return new ArrayList
    
     ();        }        return generateTrees(1,n);      }    //函数功能：树节点中的value由start~end构成的二叉搜索树的所有结果    private List
     
       generateTrees(int start, int end) {        List
      
        res=new ArrayList
       
        ();        if(end
        
          leftSubTreeList=generateTrees(start,i-1); List
         
           rightSubTreeList=generateTrees(i+1,end); //遍历并由根节点组合左子树和右子树构成最后的结果 for(TreeNode leftSubTree:leftSubTreeList){ for(TreeNode rightSubTree:rightSubTreeList){ TreeNode root=new TreeNode(i); root.left=leftSubTree; root.right=rightSubTree; res.add(root); } } } return res; }}
         
        
       
      
     
    
   

转载地址：http://zxuoi.baihongyu.com/