95,96的思路是一致的

代码

class Solution {
    public List<TreeNode> generateTrees(int n) {
        if(n == 0) return new ArrayList();
        return dfs(1, n);
    }

    public List<TreeNode> dfs(int l, int r){
        List<TreeNode> res = new ArrayList();
        if(l > r) {res.add(null); return res;}

        //枚举根结点
        for(int i = l; i <= r; i++){
            List<TreeNode> left = dfs(l, i-1);
            List<TreeNode> right = dfs(i+1, r);
            for(TreeNode tl: left){
                for(TreeNode tr: right){
                    TreeNode root = new TreeNode(i);
                    root.left = tl; root.right = tr;
                    res.add(root);
                }
            }
        }

        return res;
    }
}