Leetcode 动态规划

95. 不同的二叉搜索树II

题目大意

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例：

image.png

分析

采用递归的思想。递归函数设计为help(start,end)，返回[start,end]这个序列的所有二叉搜索树的根节点集合。假设我们有一个序列[1,100], 取i=35作为根节点。那么i的左子树的根节点，应该是从help(1,34)中随机选择一个节点。i的右子树的根，就是从help(36,100)中随机选择一个节点。

代码

//方法一：递归  39.44%
    public List<TreeNode> generateTrees(int n) {
        if(n<=0) return new LinkedList<TreeNode>();
        else return help(1,n);
    }

    //返回[start,end]序列的全部二叉搜索树
    private List<TreeNode> help(int start,int end) {
        List<TreeNode> res = new LinkedList<>();
        if(start > end) {
            res.add(null);
            return res;
        };

        for(int i=start;i<=end;i++) {  //选择根节点
            List<TreeNode> left = help(start,i-1);  
            List<TreeNode> right = help(i+1,end);   
            
            for(TreeNode l:left) {
                for(TreeNode r:right) {
                    TreeNode curRoot = new TreeNode(i);
                    curRoot.left = l;
                    curRoot.right = r;
                    res.add(curRoot);
                }
            }
        } 
        return res;
    }

96. 不同的二叉搜索树

题目大意

给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？
示例：

image.png

分析

与上一题类似，这里我们需要理清楚二叉搜索树的数量关系。二叉搜索树的数量只与节点的数量有关，也就是说[2..5]的二叉搜索树的数量和[100,103]的数量是一致的。为了避免重复运算，用一个map记录节点数和二叉搜索树数量的映射关系。

代码一

 HashMap<Integer,Integer> map = new HashMap<>();
    public int numTrees(int n) {
        if(n<=0) return 0;
        return help(1,n);
    }

    private int help(int start,int end) {
        if(map.containsKey(end-start)) return map.get(end-start);
        if(start > end) return 1;
        int sum = 0;
        for(int i=start;i<=end;i++) {
            int leftSize = help(start,i-1);
            int rightSize = help(i+1,end);
            sum += leftSize*rightSize; 
        }
        map.put(end-start,sum);
        return map.get(end-start);
    }

代码二

还可以利用动态规划的思想，dp[i]存储的是，节点数为i的二叉搜索树有多少。dp[i] = dp[左子树的规模]*dp[右子树的规模]。

//方法二：动态规划
    public int numTrees(int n) {
        if(n<=0) return 0;
        int[] dp = new int[n+1];
        dp[0] = 1;

        for(int i =1;i<=n;i++)  {   //总共的节点数
            for(int j = 1;j<=i;j++) {  //左子树的节点数
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }