题解 | #不同的二叉搜索树 ii#

1. 判断函数终止时，null值加入到res中很关键。
2. 选定某个根节点时，递归得到他所有可能的左子树和右子树。
3. 同一根节点下的左子树和右子树可以任意组合。
4. 得到最后的res。

public class Solution {
    public ArrayList<TreeNode> generateTrees (int n) {
        return help(1,n);
    }

    public ArrayList<TreeNode> help(int start , int end){

        ArrayList<TreeNode> res = new ArrayList<>();

        if(start > end)
        {
            res.add(null);
            return res;
        }

        for(int i = start ; i <= end ; i++)
        {
            ArrayList<TreeNode> left = help(start,i-1);
            ArrayList<TreeNode> right = help(i+1,end);

            for(TreeNode l : left)
            {
                for(TreeNode r : right)
                {
                    TreeNode root = new TreeNode(i);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }

        }
        return res;
    }
}