import java.util.ArrayList;
import java.util.List;

public class _95 {
    static class Solution1 {
        public List<TreeNode> generateTrees(int n) {
            return helper(1, n);
        }

        public List<TreeNode> helper(int s, int e) {
            //别人的递归思路，不好理解。
            List<TreeNode> res = new ArrayList<>();
            if (s > e) {
                res.add(null);
                return res;
            }
            for (int i = s; i <= e; i++) {
                List<TreeNode> leftNodes = helper(s, i - 1);
                List<TreeNode> rightNodes = helper(i + 1, e);
                for (TreeNode left : leftNodes) {
                    for (TreeNode right : rightNodes) {
                        res.add(new TreeNode(i, left, right));
                    }
                }
            }
            return res;
        }
    }
}